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

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)