Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models

Abstract

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model. Let ${\lambda }_c(T_{\Delta })$ denote the critical activity for the hard-model on the infinite $\Delta$-regular tree. Weitz presented an FPTAS for the partition function when $\lambda <{\lambda }_c(T_{\Delta })$ for graphs with constant maximum degree $\Delta$. In contrast, Sly showed that for all $\Delta \ge 3$, there exists ${\epsilon }_{\Delta }>0$ such that (unless RP=NP) there is no FPRAS for approximating the partition function on graphs of maximum degree $\Delta$ for activities $\lambda$ satisfying ${\lambda }_c(T_{\Delta })<\lambda <{\lambda }_c(T_{\Delta })+{\epsilon }_{\Delta }$. We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Recent results of Li et al. and Sinclair et al. extend Weitz's approach to any 2-spin model, which includes the antiferromagnetic Ising model, to yield an FPTAS for the partition function for all graphs of constant maximum degree $\Delta$ when the parameters of the model lie in the uniqueness regime of the infinite tree $T_{\Delta }$. We prove the complementary result that for the antiferrogmanetic Ising model without external field that, unless RP=NP, for all $\Delta \ge 3$, there is no FPRAS for approximating the partition function on graphs of maximum degree $\Delta$ when the inverse temperature lies in the non-uniqueness regime of the infinite tree $T_{\Delta }$. Our results extend to a region of the parameter space for general 2-spin models. Our proof works by relating certain second moment calculations for random $\Delta$-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

Journal version (no changes)

References in corpus (2)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The computational hardness of counting in two-spin models on d-regular graphs

Cited by in corpus (42)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• The computational hardness of counting in two-spin models on d-regular graphs
• Algorithmic Pirogov-Sinai theory
• #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• FPTAS for Counting Monotone CNF
• Efficient Algorithms for Approximating Quantum Partition Functions
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• A Simple FPTAS for Counting Edge Covers
• Collective Monte Carlo updates through tensor network renormalization
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• Calculating eigenvalues of many-body systems from partition functions
• Algorithmic Cluster Expansions for Quantum Problems
• Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
• Efficient Algorithms for Approximating Quantum Partition Functions at Low Temperature
• An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
• Uniform Sampling through the Lovász Local Lemma
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
• What can be sampled locally?
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• Uniqueness of the Gibbs measure for the $4$-state anti-ferromagnetic Potts model on the regular tree
• Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
• More on zeros and approximation of the Ising partition function
• Approximating the partition function of planar two-state spin systems
• Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
• Perfect sampling from spatial mixing
• Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin
• Fundamentals of Partial Rejection Sampling
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite $\Delta$-regular tree for large $\Delta$
• Spatial mixing and approximate counting for Potts model on graphs with bounded average degree
• Approximate Counting, the Lovasz Local Lemma and Inference in Graphical Models
• Algorithms for the ferromagnetic Potts model on expanders
• Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models
• Rapid Mixing for Colorings via Spectral Independence
• Uniformly Random Colourings of Sparse Graphs
• Zeros of ferromagnetic 2-spin systems
• From Boltzmann Machines to Neural Networks and Back Again
• Fast and Slow Mixing of the Kawasaki Dynamics on Bounded-Degree Graphs
• Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
• Entropic Independence II: Optimal Sampling and Concentration via Restricted Modified Log-Sobolev Inequalities
• Markov chains for tensor network states