\(\#\)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

zbMATH Keywords

complexityphase transitionspin systemsapproximate counting\(\#\)BIS-hardness

Mathematics Subject Classification ID

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

Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, An FPTAS for the hardcore model on random regular bipartite graphs, Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function, Algorithmic Pirogov-Sinai theory, What can be sampled locally?, Approximation Algorithms for the Random Field Ising Model, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, Counting Constraint Satisfaction Problems., Algorithms for #BIS-Hard Problems on Expander Graphs, A fixed-parameter perspective on \#BIS, Unnamed Item, Unnamed Item, Weighted counting of solutions to sparse systems of equations, Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results, Unnamed Item

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