Computational Transition at the Uniqueness Threshold

2010/05/31 by Sly, Allan · 5 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR)

paper · doi:10.48550/arxiv.1005.5584

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 = \frac(d-1)^d-1(d-2)^d is the uniqueness threshold on the d-regular tree and ε(d)>0. Weitz produced an FPTAS for approximating the partition function when 0

Cited by

• A phase transition for the hard sphere model on the hyperbolic plane
• From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
• Estimating Ising Models in Total Variation Distance
• Congested Clique Counting for Local Gibbs Distributions
• Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence

Related

• Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
• Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets
• Improved Mixing of Critical Hardcore Model
• Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model
• Uniqueness and Rapid Mixing in the Bipartite Hardcore Model