The computational hardness of counting in two-spin models on d-regular graphs

Abstract

The class of two-spin systems contains several important models, including random independent sets and the Ising model of statistical physics. We show that for both the hard-core (independent set) model and the anti-ferromagnetic Ising model with arbitrary external field, it is NP-hard to approximate the partition function or approximately sample from the model on d-regular graphs when the model has non-uniqueness on the d-regular tree. Together with results of Jerrum--Sinclair, Weitz, and Sinclair--Srivastava--Thurley giving FPRAS's for all other two-spin systems except at the uniqueness threshold, this gives an almost complete classification of the computational complexity of two-spin systems on bounded-degree graphs. Our proof establishes that the normalized log-partition function of any two-spin system on bipartite locally tree-like graphs converges to a limiting "free energy density" which coincides with the (non-rigorous) Bethe prediction of statistical physics. We use this result to characterize the local structure of two-spin systems on locally tree-like bipartite expander graphs, which then become the basic gadgets in a randomized reduction to approximate MAX-CUT. Our approach is novel in that it makes no use of the second moment method employed in previous works on these questions.

23 pages

References in corpus (5)

• Ising models on locally tree-like graphs
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Ising models on power-law random graphs
• Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
• Correlation Decay up to Uniqueness in Spin Systems

Cited by in corpus (31)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction
• A Simple FPTAS for Counting Edge Covers
• Correlation Decay up to Uniqueness in Spin Systems
• Contraction: a Unified Perspective of Correlation Decay and Zero-Freeness of 2-Spin Systems
• Extremal regular graphs: the case of the infinite regular tree
• Uniform Sampling through the Lovász Local Lemma
• Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region
• Hardness of parameter estimation in graphical models
• The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• Optimal Mixing of Glauber Dynamics: Entropy Factorization via High-Dimensional Expansion
• Counting hypergraph matchings up to uniqueness threshold
• Optimal Mixing Time for the Ising Model in the Uniqueness Regime
• Zero-free regions of partition functions with applications to algorithms and graph limits
• FPTAS for Hardcore and Ising Models on Hypergraphs
• The Vertex Sample Complexity of Free Energy is Polynomial
• The replica symmetric solution for Potts models on d-regular graphs
• Spatial mixing and approximate counting for Potts model on graphs with bounded average degree
• Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
• Lee-Yang theorems and the complexity of computing averages
• Approximate maximum entropy principles via Goemans-Williamson with applications to provable variational methods
• Zeros of ferromagnetic 2-spin systems
• Rapid Mixing for Colorings via Spectral Independence
• Zeros of Holant problems: locations and algorithms
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• FPTAS for Weighted Fibonacci Gates and Its Applications
• Spatial Mixing and Systematic Scan Markov chains
• Learning to Sample from Censored Markov Random Fields
• Spatial Mixing for Independent Sets in Poisson Random Trees