\#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

DOI10.1016/J.JCSS.2015.11.009zbMATH Open1338.68086arXiv1311.4451OpenAlexW1770469170MaRDI QIDQ269470FDOQ269470

Authors: Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Eric Vigoda, Mark Jerrum, D. Štefankovič 

Publication date: 18 April 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Abstract: Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. As a consequence, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.

Full work available at URL: https://arxiv.org/abs/1311.4451

Recommendations

• \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• Counting in two-spin models on \(d\)-regular graphs
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs

zbMATH Keywords

phase transitioncomplexityapproximate counting\(\#\)BIS-hardnessspin systems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Cites Work

• Gibbs measures and phase transitions.
• On the hardness of sampling independent sets beyond the tree threshold
• The relative complexity of approximate counting problems
• Holant problems and counting CSP
• An effective dichotomy for the counting constraint satisfaction problem
• A graph polynomial for independent sets of bipartite graphs
• 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
• The Complexity of Ferromagnetic Ising with Local Fields
• The Complexity of the Counting Constraint Satisfaction Problem
• Title not available (Why is that?)
• A counterexample to rapid mixing of the Ge-Stefankovic process
• The computational complexity of two‐state spin systems
• 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
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• Approximating the partition function of planar two-state spin systems
• An approximation trichotomy for Boolean \#CSP

Cited In (20)

• Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• A fixed-parameter perspective on \#BIS
• A fixed-parameter perspective on \#BIS
• \#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
• Fast algorithms for general spin systems on bipartite expanders
• Approximation Algorithms for the Random Field Ising Model
• Counting constraint satisfaction problems
• FPTAS for \#BIS with degree bounds on one side
• Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function
• An FPTAS for the hardcore model on random regular bipartite graphs
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
• Weighted counting of solutions to sparse systems of equations
• Algorithmic Pirogov-Sinai theory
• What can be sampled locally?
• The complexity of ferromagnetic 2-spin systems on bounded degree graphs
• Algorithms for \#BIS-hard problems on expander graphs
• Hardness of identity testing for restricted Boltzmann machines and Potts models
• The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs

This page was built for publication: \(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q269470)