@inproceedings{4706225d24b040ae82d4b41869e9c34c,
title = "Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model",
abstract = "We study the hard-core (gas) model defined on independent sets of an input graph where the independent sets are weighted by a parameter (aka fugacity) λ > 0. For constant δ, previous work of Weitz (2006) established an FPTAS for the partition function for graphs of maximum degree δ when λλc(δ). The threshold λc(δ) is the critical point for the statistical physics phase transition for uniqueness/non-uniqueness on the infinite δ-regular tree. The running time of Weitz's algorithm is exponential in logδ. Here we present an FPRAS for the partition function whose running time is O∗(n2). We analyze the simple single-site Markov chain known as the Glauber dynamics for sampling from the associated Gibbs distribution. We prove there exists a constant δ0 such that for all graphs with maximum degree δ ≥ δ0 and girth ≥ 7 (i.e., no cycles of length ≤ 6), the mixing time of the Glauber dynamics is O(n log n) when λ.",
keywords = "Belief Propagation, Convergence, Gibbs Tree Uniqueness, Hard-Core model, MCMC, Rapid mixing",
author = "Charilaos Efthymiou and Hayes, \{Thomas P.\} and Daniel Stefankovic and Eric Vigoda and Yitong Yin",
note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 ; Conference date: 09-10-2016 Through 11-10-2016",
year = "2016",
month = dec,
day = "14",
doi = "10.1109/FOCS.2016.80",
language = "English",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "704--713",
booktitle = "Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016",
address = "United States",
}