Dec. 1, 3:30pm, Wean 8220

Eric Vigoda, Georgia Tech

Phase transitions, Markov chains, and BP

Eric Vigoda, Georgia Tech

Phase transitions, Markov chains, and BP

Abstract:

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 the algorithmic result is
due to Weitz (2006), but the drawback 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
which appeared in FOCS '16.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.