The complexity of approximating conservative counting CSPs

DOI10.4230/LIPICS.STACS.2013.148MaRDI QIDQ2957879zbMATH OpenOpenAlexFDO

Authors Xi Chen, Martin Dyer, Leslie Ann Goldberg, Pinyan Lu, Colin McQuillan, David Richerby, Mark Jerrum

Publication date 30 January 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.STACS.2013.148

zbMATH Keywords

complexityapproximationcounting constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity of approximating conservative counting CSPs
• scientific article; zbMATH DE number 7204479
• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• An approximation trichotomy for Boolean \#CSP

Cited in

(12)

• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Counting problems in parameterized complexity
• Log-supermodular functions, functional clones and counting CSPs
• The complexity of approximating conservative counting CSPs
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• Descriptive Complexity of approximate counting CSPs
• Holant clones and the approximability of conservative holant problems
• Approximate Counting CSP Seen from the Other Side
• scientific article; zbMATH DE number 7561704 (Why is no real title available?)
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

This page was built for publication: The complexity of approximating conservative counting CSPs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2957879)