Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
Georgia Tech Title: Phase transitions, Markov chains, and BP Abstract: For counting weighted independent sets weighted by a parameter $\lambda$ (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 $\lambda$ 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. Date: Thursday, December 1, 2016 Time: 3:30 pm Location: Wean Hall 8220 |