#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region

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.

References in corpus (4)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The complexity of approximating conservative counting CSPs
• The Complexity of Ferromagnetic Two-spin Systems with External Fields
• Approximating the partition function of planar two-state spin systems

Cited by in corpus (9)

• Algorithmic Pirogov-Sinai theory
• FPTAS for #BIS with Degree Bounds on One Side
• Weighted counting of solutions to sparse systems of equations
• What can be sampled locally?
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
• Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems
• Approximation algorithms for the random-field Ising model
• Any Finite Distributive Lattice is Isomorphic to the Minimizer Set of an ${\mathrm{M}}^{♮}$-Concave Set Function