The complexity of approximating conservative counting CSPs

DOI10.4230/LIPICS.STACS.2013.148zbMATH Open1354.68115OpenAlexW2518351639MaRDI QIDQ2957879FDOQ2957879

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

Publication date: 30 January 2017

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

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
• Approximate counting for complex-weighted Boolean constraint satisfaction problems

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)

Cited In (7)

• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• The complexity of counting locally maximal satisfying assignments of Boolean CSPs
• Descriptive Complexity of approximate counting CSPs
• Approximate Counting CSP Seen from the Other Side
• Title not available (Why is that?)
• Title not available (Why is that?)

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)