Analyzing Markov Chains using Belief Propagation


Eric Vigoda

Monday, May 8th, 2017
4:00pm Malott 406* Room Change




For counting weighted independent sets weighted by a parameter λ (known as the hard-core model) there is a beautiful connection between statistical physics phase transitions on infinite, regular trees and the computational complexity of approximate counting on graphs of maximum degree D. For λ below the critical point there is an elegant algorithm devised by Weitz (2006). The drawback of his algorithm is that the running time is exponential in log D. In this talk we’ll describe recent work which shows O(n log n) mixing time of the single-site Markov chain when the girth>6 and D is at least a sufficiently large constant. Our proof utilizes BP (belief propagation) to design a distance function in our coupling analysis.

This is joint work with C. Efthymiou, T. Hayes, D. Stefankovic, and Y. Yin, see: