The complexity of approximating conservative counting CSPs
From MaRDI portal
Publication:2957879
DOI10.4230/LIPICS.STACS.2013.148zbMATH Open1354.68115OpenAlexW2518351639MaRDI QIDQ2957879FDOQ2957879
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
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (12)
- 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
- 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
- Title not available (Why is that?)
- 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)
