Computational Transition at the Uniqueness Threshold

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 st- - atistical physics phase transitions.