The complexity of Boolean #MaximalCSP.

Leslie Ann Goldberg, Mark Jerrum

Type: Preprint

Publication Date: 2015-09-11

Citations: 0

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	The complexity of counting locally maximal satisfying assignments of Boolean CSPs	2016	Leslie Ann Goldberg Mark Jerrum
+	Nonnegative Weighted #CSP: An Effective Complexity Dichotomy	2016	Jin‐Yi Cai Xi Chen Pinyan Lu
+	The complexity of approximating conservative counting CSPs.	2013	Xi Chen Martin Dyer Leslie Ann Goldberg Mark Jerrum Pinyan Lu Colin McQuillan David Richerby
+	Non-negative Weighted #CSPs: An Effective Complexity Dichotomy	2010	Jin‐Yi Cai Xi Chen Pinyan Lu
+	Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems	2017	Andreas Galanis Leslie Ann Goldberg Kuan Yang
+ PDF Chat	Non-negatively Weighted #CSP: An Effective Complexity Dichotomy	2011	Jin‐Yi Cai Xi Chen Pinyan Lu
+	Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems	2016	Andreas Galanis Leslie Ann Goldberg Kuan Yang
+ PDF Chat	Log-supermodular functions, functional clones and counting CSPs	2012	Andreĭ A. Bulatov Martin Dyer Leslie Ann Goldberg Mark Jerrum
+ PDF Chat	Complexity of Counting CSP with Complex Weights	2017	Jin‐Yi Cai Xi Chen
+	Guest column	2011	X. Chen
+	Complexity of Counting CSP with Complex Weights	2011	Jin‐Yi Cai Xi Chen
+ PDF Chat	Complexity of counting CSP with complex weights	2012	Jin‐Yi Cai Xi Chen
+	Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints	2022	Eun Jung Kim Stefan Kratsch Marcin Pilipczuk Magnus Wahlström
+ PDF Chat	Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems	2024	Tomoyuki Yamakami
+	Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds: A Survey	2011	Gregory Gutin Anders Yeo
+	The Complexity of Modular Counting in Constraint Satisfaction Problems.	2012	John Faben
+ PDF Chat	Optimal Polynomial-Time Compression for Boolean Max CSP	2023	Bart M. P. Jansen Michał Włodarczyk
+	The \#CSP Dichotomy is Decidable	2011	Martin Dyer David Richerby
+ PDF Chat	Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints	2023	Eun Jung Kim Stefan Kratsch Marcin Pilipczuk Magnus Wahlström
+ PDF Chat	Bounded Degree Nonnegative Counting CSP	2023	Jin‐Yi Cai Daniel P. Szabo

Works That Cite This (0)

Action	Title	Year	Authors

Works Cited by This (5)

Action	Title	Year	Authors
+ PDF Chat	An approximation trichotomy for Boolean #CSP	2009	Martin Dyer Leslie Ann Goldberg Mark Jerrum
+	Complexity of counting the optimal solutions	2009	Miki Hermann Reinhard Pichler
+	The complexity of computing the permanent	1979	Leslie G. Valiant
+	The Complexity of Enumeration and Reliability Problems	1979	Leslie G. Valiant
+ PDF Chat	The Relative Complexity of Approximate Counting Problems	2003	Martin Dyer Leslie Ann Goldberg Catherine Greenhill Mark Jerrum