\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
DOI10.1016/j.jcss.2015.11.009zbMath1338.68086arXiv1311.4451OpenAlexW1770469170MaRDI QIDQ269470
Andreas Galanis, Jin-Yi Cai, Leslie Ann Goldberg, Eric Vigoda, Heng Guo, Mark R. Jerrum, Daniel Štefanković
Publication date: 18 April 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4451
Analysis of algorithms and problem complexity (68Q25) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A counterexample to rapid mixing of the Ge-Stefankovic process
- Gibbs measures and phase transitions.
- Approximating the partition function of planar two-state spin systems
- An approximation trichotomy for Boolean \#CSP
- On the hardness of sampling independent sets beyond the tree threshold
- The relative complexity of approximate counting problems
- An Effective Dichotomy for the Counting Constraint Satisfaction Problem
- Improved inapproximability results for counting independent sets in the hard-core model
- Counting independent sets up to the tree threshold
- The complexity of approximating conservative counting CSPs.
- The Complexity of Ferromagnetic Two-spin Systems with External Fields
- Polynomial-Time Approximation Algorithms for the Ising Model
- Inapproximability after Uniqueness Phase Transition in Two-Spin Systems
- Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region
- The Complexity of Ferromagnetic Ising with Local Fields
- The Complexity of the Counting Constraint Satisfaction Problem
- Approximating the Partition Function of the Ferromagnetic Potts Model
- The computational complexity of two‐state spin systems
- Holant problems and counting CSP
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- The expressibility of functions on the boolean domain, with applications to counting CSPs
- Complexity of counting CSP with complex weights
- On Unapproximable Versions of $NP$-Complete Problems
- Correlation Decay up to Uniqueness in Spin Systems
- Approximate Counting via Correlation Decay in Spin Systems