Browse Conferences > Foundations of Computer Scien...

Computational Transition at the Uniqueness Threshold

Efficient simulation of space-time correlated MIM...

Kalman filtering and smoothing solutions to tempo...

Optimality and Complexity of Opportunistic Spectr...

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 $I$ of a graph weighted proportionally to

λ|I| $\lambda^{|I|}$ with fugacity parameter

λ $\lambda$ . We prove that at the uniqueness threshold of the hardcore model on the

d $d$ -regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree

d $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 $d$ for fugacity

λc(d)0 $\lambda_c(d) 0$ . Weitz produced an FPTAS for approximating the partition function when $0

Published in: Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on

Date of Conference: 23-26 Oct. 2010

Date Added to IEEE Xplore: 17 December 2010

Print ISBN: 978-1-4244-8525-3

Print ISSN: 0272-5428

INSPEC Accession Number: 11699091

DOI: 10.1109/FOCS.2010.34

Publisher: IEEE

Alerts

Read the full document

Keywords

IEEE Keywords
Approximation methods, Computational modeling, Physics, Correlation, Polynomials, Phase measurement, Markov processes
INSPEC: Controlled Indexing
trees (mathematics), computational complexity, function approximation, phase transformations, set theory, statistical distributions
INSPEC: Non-Controlled Indexing
random bipartite graph, uniqueness threshold, hardcore model, lattice gas system, probability distribution, set theory, fugacity parameter, d-regular tree, partition becomes approximating, statistical physics phase transition
Author Keywords
Phase Transition, Hardcore Model, Approximate counting

Authors

Allan Sly

Microsoft Res., Redmond, WA, USA

UNIVERSITY OF BATH

Computational Transition at the Uniqueness Threshold

Keywords

Authors

IEEE Account

Purchase Details

Profile Information

Need Help?