Source-linked AI summary
The computational hardness of counting in two-spin models on d-regular graphs
Allan Sly, Nike Sun
TL;DR
The paper asks how hard it is to approximate partition functions for homogeneous two-spin systems on bounded-degree graphs. It combines a free-energy and local-structure analysis with a randomized reduction to approximate MAX-CUT, proving threshold-aligned hardness and an almost complete classification, while relying on locally tree-like graph assumptions in the hardness construction.
Problem
The paper studies the computational complexity of approximating partition functions for homogeneous two-spin systems on bounded-degree graphs, including hard-core and anti-ferromagnetic Ising models.
Method
The proof establishes Bethe-predicted free-energy limits and uses local structure on locally tree-like bipartite expanders as gadgets in a randomized reduction to approximate MAX-CUT, without second-moment calculations.
Results
The computational transition occurs at the d-regular tree uniqueness threshold, and the combined results classify homogeneous two-spin systems on d-regular graphs except at uniqueness thresholds.
Takeaways & Limitations
Non-uniqueness regimes are computationally hard, while prior algorithms cover the remaining regimes, giving an almost complete complexity classification.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper locates the computational transition for anti-ferromagnetic two-spin systems on d-regular graphs at the corresponding tree uniqueness threshold. It proves hardness in the non-uniqueness regime and, together with prior algorithms, nearly classifies homogeneous two-spin systems except at threshold cases.
- Main results: The computational transition for anti-ferromagnetic models on d-regular graphs occurs precisely at the corresponding d-regular tree’s uniqueness threshold.This covers the hard-core model and anti-ferromagnetic Ising models with external fields.
- Hard-core model: Above the hard-core threshold λc(d), approximating the partition function is NP-hard, while prior work gives an FPTAS below λc(d).The threshold marks when distant boundary conditions can retain nonvanishing influence at the tree root.
- Proof approach: The proof uses a conceptual approach that avoids the second moment method and extends the threshold result to anti-ferromagnetic Ising models with arbitrary external field.Earlier work relied on difficult second-moment calculations that imposed a technical restriction near the hard-core threshold.
- Anti-ferromagnetic Ising model: Below βc,af(B, d), no FPRAS exists for the anti-ferromagnetic Ising partition function with arbitrary external field B unless NP = RP.The theorem applies for d ≥ 3 and β < βc,af(B, d) < 0.
- Classification: The hard-core and anti-ferromagnetic Ising models cover all non-degenerate homogeneous two-spin systems on d-regular graphs, yielding a full classification except at uniqueness thresholds.The classification combines the paper’s hardness theorems with earlier approximation schemes.
- Hardness strength: In non-uniqueness regimes, the hardness is strong: approximating the partition function within e^{cn} is NP-hard for some c > 0.This rules out an FPRAS and establishes hardness even for exponentially large approximation factors.
Independent results of Galanis–ˇStefankoviˇc–Vigoda.
The paper develops rigorous free-energy and local-structure results for two-spin systems on bipartite locally tree-like graphs, supporting a randomized reduction to approximate MAX-CUT. These results provide the basis for analyzing phase behavior and establishing computational hardness without the second moment method.
- Local structure: The proof characterizes local spin distributions on symmetric bipartite d-regular locally tree-like graphs through their limiting Gibbs measures on the d-regular tree.Under edge expansion and tree non-uniqueness, configurations divide into + and − phases with a linear imbalance between the graph sides.
- Reduction: Conditioned on a gadget’s global phase, spins at distant vertices become asymptotically independent with marginals determined by the gadget side.This property follows from the local-structure theorem and is used in the reduction.
- Reduction: The reduction replaces each vertex of a 3-regular MAX-CUT instance with a large bipartite d-regular gadget and connects corresponding sides while preserving regularity.The resulting neighboring gadgets prefer opposing phases because the interaction is anti-ferromagnetic.
- Reduction: For sufficiently large gadgets, the model’s partition function determines a (1+ε)-approximation of MAX-CUT.The partition-function estimate for fixed gadget phases incurs only an e^{ε|H|} multiplicative factor.
- Methodological contribution: The paper’s results establish local convergence and phase structure using precise partition-function asymptotics rather than the second moment method used in earlier work.The paper presents these asymptotics as independently interesting because partition-function lower bounds are generally challenging.
- Free energy: The normalized log-partition function converges to a free energy density equal to the Bethe prediction for any non-degenerate homogeneous two-spin model on bipartite d-regular locally tree-like graphs.This asymptotic result is used to derive the local-structure characterization.
Outline of the paper.
The paper first develops the Bethe free-energy result, then derives local structure, proves approximate conditional independence, and uses it in a randomized reduction to MAX-CUT.
- Section 2: Section 2 reviews the d-regular Bethe prediction and proves the free-energy theorem.
- Section 3: Section 3 derives the local-structure theorem from the free-energy result using methods from prior work.
- Section 4: Section 4 proves approximate conditional independence and demonstrates the randomized reduction to MAX-CUT.
2. Partition function for two-spin models
This section establishes the Bethe free-energy framework for locally tree-like two-spin systems and reduces non-degenerate models to Ising or hard-core forms. It then characterizes the relevant fixed points and proves when the limiting free energy equals the Bethe prediction.
- Free-energy framework: The proof establishes the free-energy density and verifies the Bethe prediction for two-spin models on graph sequences converging locally to the d-regular tree.The argument reduces non-degenerate systems to Ising or hard-core models and evaluates those densities by interpolation.
- Bethe prediction: The Bethe prediction identifies the limiting free-energy density with a supremum of the Bethe free-energy functional over belief-propagation fixed points.Messages are mappings from oriented-edge rooted trees to probability measures, and the BP recursion defines the fixed points.
- Bethe prediction: For bipartite d-regular trees, BP fixed points correspond to fixed points of the double recursion F(2) = F ◦ F, with alternating messages h+ and h−.The corresponding fixed points are equivalent to translation-invariant Markovian Gibbs measures.
- Model reduction: Every positive two-spin specification can be parameterized as an Ising model up to an additive constant, while a hard-core parameterization covers the one-sided zero-interaction case.The remaining cases are degenerate, with directly computable free-energy densities.
- Phase structure: Above the hard-core threshold λc, three BP fixed points exist, whereas at or below λc there is a unique fixed point.The messages coincide for λ ≤ λc and separate for λ > λc.
- Free-energy evaluation: For the hard-core model, the Bethe free energy equals the limiting density for all fugacities on locally tree-like graph sequences.The same equality holds for the anti-ferromagnetic Ising model for all β and B, although the proposition also records a regime-specific upper-bound statement.
3. Local structure of measures
This section identifies the local weak limits of Gibbs measures on locally tree-like graphs. In non-uniqueness regimes, expansion selects extremal phases and constrains subsequential limits to mixtures of the two canonical measures.
- Role in reduction: The local-structure analysis is developed to support approximate conditional independence statements for the bipartite expander gadgets used in the hardness reduction.The section’s results are explicitly adapted from this structural characterization.
- Symmetric limits: On symmetric graph sequences, every subsequential local weak limit has equal contributions from the two extremal phases: ν = (ν+ + ν−)/2.Equality of the limiting root expectation with that of ν+ implies a convex combination, and graph symmetry fixes the weights.
- Local weak limits: Any subsequential local weak limit of the plus-phase measures is a convex combination (1 − q)ν+ + qν− of the two extremal tree measures.The free-energy convergence and the preceding structural lemma yield this mixture representation.
- Phase selection: For bipartite expander graphs in the non-uniqueness regime, edge expansion forces q = 0 for the selected plus-phase limit.The contradiction argument uses the edge-expansion hypothesis.
4. Computational hardness
This section constructs locally tree-like bipartite expander gadgets and uses their phase behavior to reduce approximate partition-function computation to approximate MAX-CUT. The reduction yields computational hardness on d-regular graphs.
- Phase behavior: The gadget construction preserves the phase information needed to approximate conditional independence after terminal edges are deleted.The proof analyzes neighborhoods of terminals and the independence of their boundary spins under extremal measures.
- Gadget construction: The constructed graphs are bipartite double covers of configuration-model graphs, with selected edges removed to create constant-size terminal sets.The resulting graphs are d-regular with probability bounded away from zero as n →∞.
- Gadget construction: For fixed k and every δ > 0, the gadgets are (δ, 1/2, λδ)-edge expanders with high probability as n →∞.Expansion is established by bounding the probability of poorly expanding vertex subsets.
- Reduction: For an input 3-regular graph H, copies of the gadget are connected along terminal sets to form a new d-regular graph HG.The connections encode whether adjacent vertices of H receive the same or different phases.
- Reduction: In anti-ferromagnetic non-uniqueness regimes, the phase-alignment and phase-disagreement weights satisfy Θ > Γ, making cut edges exponentially distinguishable in the gadget partition function.The resulting bounds relate ZHG to (Θ/Γ) raised to a power determined by max-cut(H).
- Hardness conclusion: An approximation to ZHG within a factor of e^{c|HG|} would yield arbitrarily accurate multiplicative estimates of max-cut(H), contradicting NP-hardness of approximate MAX-CUT.The reduction uses k large and c small to make the upper and lower bounds differ by an arbitrarily small multiplicative error.