Algorithmic Pirogov-Sinai theory

Seminar | February 20 | 3-4 p.m. | 1011 Evans Hall

 Will Perkins, University of Illinois at Chicago

 Department of Statistics

What is the connection between a phase transition in a statistical physics model and the computational complexity of sampling from the given model? In the setting of the hard-core and Potts models on lattices, it is known that in the phase coexistence regime the Glauber dynamics mix slowly. Using some of the same tools used to prove slow mixing (the cluster expansion and Pirogov-Sinai theory), we give efficient algorithms to approximate the partition function of and sample from the hard-core and Potts models at sufficiently low temperatures on the lattice. Our algorithms are inspired by Barvinok's approach to polynomial approximation. Joint work with Tyler Helmuth and Guus Regts.

 sganguly@berkeley.edu