Computational Transition at the Uniqueness Threshold
Author:
- Allan SlyASAllan Sly
- 1 October 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 287-296
Abstract
The hardcore model is a model of lattice gas systems which has received much attention in statistical physics, probability theory and theoretical computer science. It is the probability distribution over independent sets I of a graph weighted proportionally to λ |I| with fugacity parameter λ. We prove that at the uniqueness threshold of the hardcore model on the d-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree d. Specifically, we show that unless NP = RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree d for fugacity λ c (d) <; λ <; λ c (d) + ε(d) where λ c = (d - 1) d-1 /(d - 2) d is the uniqueness threshold on the d-regular tree and ε(d) > 0 is a positive constant. Weitz [36] produced an FPTAS for approximating the partition function when 0 <; λ <; λ c (d) so this result demonstrates that the computational threshold exactly coincides with the statistical physics phase transition thus confirming the main conjecture of [30]. We further analyze the special case of λ = 1, d = 6 and show there is no polynomial time approximation scheme for approximately counting independent sets on graphs of maximum degree d = 6, which is optimal, improving the previous bound of d = 24. Our proof is based on specially constructed random bipartite graphs which act as gadgets in a reduction to MAX-CUT. Building on the involved second moment method analysis of [30] and combined with an analysis of the reconstruction problem on the tree our proof establishes a strong version of "replica" method heuristics developed by theoretical physicists. The result establishes the first rigorous correspondence between the hardness of approximate counting and sampling with statistical physics phase transitions.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Ising models on locally tree-like graphsThe Annals of Applied Probability, 2010
- Uniqueness thresholds on trees versus graphsThe Annals of Applied Probability, 2008
- On the hardness of sampling independent sets beyond the tree thresholdProbability Theory and Related Fields, 2008
- Gibbs states and the set of solutions of random constraint satisfaction problemsProceedings of the National Academy of Sciences, 2007
- Fast mixing for independent sets, colorings, and other models on treesRandom Structures & Algorithms, 2006
- Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphsRandom Structures & Algorithms, 2005
- Polynomial-time approximation algorithms for the ising model2005
- Glauber dynamics on trees and hyperbolic graphsProbability Theory and Related Fields, 2004
- Robust reconstruction on trees is determined by the second eigenvalueThe Annals of Probability, 2004
- On Markov Chains for Independent SetsJournal of Algorithms, 2000