The complexity of complex weighted Boolean #CSP

Jin‐Yi Cai, Pinyan Lu, Mingji Xia

Type: Article

Publication Date: 2013-07-24

Citations: 64

DOI: https://doi.org/10.1016/j.jcss.2013.07.003

View Publication

Locations

Journal of Computer and System Sciences - View
CiteSeer X (The Pennsylvania State University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Holographic algorithm with matchgates is universal for planar #CSP over boolean domain	2017	Jin‐Yi Cai Zhiguo Fu
+	The Exponential-Time Complexity of the complex weighted #CSP	2022	Ying Liu
+ PDF Chat	Complexity of Counting CSP with Complex Weights	2017	Jin‐Yi Cai Xi Chen
+ PDF Chat	Complexity of counting CSP with complex weights	2012	Jin‐Yi Cai Xi Chen
+	Holographic Algorithm with Matchgates Is Universal for Planar $\#$CSP Over Boolean Domain	2016	Jin‐Yi Cai Zhiguo Fu
+	Exponential Time Complexity of the Complex Weighted Boolean #CSP	2023	Ying Liu
+	A dichotomy theorem for the approximate counting of complex-weighted bounded-degree Boolean CSPs	2012	Tomoyuki Yamakami
+ PDF Chat	From Holant to #CSP and Back: Dichotomy for Holant c Problems	2010	Jin‐Yi Cai Sangxia Huang Pinyan Lu
+	From Holant To #CSP And Back: Dichotomy For Holant$^c$ Problems	2010	Jin‐Yi Cai Sangxia Huang Pinyan Lu
+	Complexity of Counting CSP with Complex Weights	2011	Jin‐Yi Cai Xi Chen
+	Nonnegative Weighted #CSP: An Effective Complexity Dichotomy	2016	Jin‐Yi Cai Xi Chen Pinyan Lu
+	Dichotomy for Holant problems of Boolean domain	2011	Jin‐Yi Cai Pinyan Lu Mingji Xia
+ PDF Chat	Dichotomy for Holant∗ Problems on the Boolean Domain	2020	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	Holant problems and counting CSP	2009	Jin‐Yi Cai Pinyan Lu Mingji Xia
+ PDF Chat	A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs	2010	Tomoyuki Yamakami
+ PDF Chat	A Complete Dichotomy Rises from the Capture of Vanishing Signatures	2016	Jin‐Yi Cai Heng Guo Tyson Williams
+ PDF Chat	A complete dichotomy rises from the capture of vanishing signatures	2013	Jin‐Yi Cai Heng Guo Tyson Williams
+ PDF Chat	The complexity of planar Boolean #CSP with complex weights	2019	Heng Guo Tyson Williams
+ PDF Chat	The Complexity of Planar Boolean #CSP with Complex Weights	2013	Heng Guo Tyson Williams
+	A Complete Dichotomy Rises from the Capture of Vanishing Signatures	2012	Jin‐Yi Cai Heng Guo Tyson Williams

Works That Cite This (60)

Action	Title	Year	Authors
+ PDF Chat	Holographic Algorithms Beyond Matchgates	2014	Jin‐Yi Cai Heng Guo Tyson Williams
+	The Complexity of Boolean Holant Problems with Nonnegative Weights	2018	Jiabao Lin Hanpin Wang
+ PDF Chat	The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems	2014	Jin‐Yi Cai Heng Guo Tyson Williams
+ PDF Chat	FKT is Not Universal — A Planar Holant Dichotomy for Symmetric Constraints	2021	Jin‐Yi Cai Zhiguo Fu Heng Guo Tyson Williams
+	The Complexity of Holant Problems over Boolean Domain with Non-negative Weights	2016	Jiabao Lin Hanpin Wang
+ PDF Chat	Bounded Degree Nonnegative Counting CSP	2023	Jin‐Yi Cai Daniel P. Szabo
+	Computing and estimating the volume of the solution space of SMT(LA) constraints	2016	Cunjing Ge Feifei Ma Peng Zhang Jian Zhang
+	The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems	2014	Jin‐Yi Cai Heng Guo Tyson Williams
+ PDF Chat	The Complexity of Approximating complex-valued Ising and Tutte partition functions	2017	Leslie Ann Goldberg Heng Guo
+	Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin	2019	Miriam Backens Andreĭ A. Bulatov Leslie Ann Goldberg Colin McQuillan Stanislav Živný

Works Cited by This (23)

Action	Title	Year	Authors
+ PDF Chat	From Holant to #CSP and Back: Dichotomy for Holant c Problems	2010	Jin‐Yi Cai Sangxia Huang Pinyan Lu
+ PDF Chat	From Holant to #CSP and Back: Dichotomy for Holant c Problems	2012	Jin‐Yi Cai Sangxia Huang Pinyan Lu
+	Computational Complexity of Holant Problems	2011	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	The Complexity of Counting in Sparse, Regular, and Planar Graphs	2001	Salil Vadhan
+	Holant problems and counting CSP	2009	Jin‐Yi Cai Pinyan Lu Mingji Xia
+	The complexity of counting graph homomorphisms	2000	Martin Dyer Catherine Greenhill
+	The complexity of counting graph homomorphisms (extended abstract)	2000	Martin Dyer Catherine Greenhill
+ PDF Chat	Holographic algorithms: From art to science	2010	Jin‐Yi Cai Pinyan Lu
+	A Complexity Dichotomy for Partition Functions with Mixed Signs	2010	Leslie Ann Goldberg Martin Grohe Mark Jerrum Marc Thurley
+ PDF Chat	The complexity of weighted Boolean #CSP with mixed signs	2009	Andreǐ A. Bulatov Martin Dyer Leslie Ann Goldberg Markus Jalsenius David Richerby