Counting and sampling at low temperatures

Abstract:
We consider the problem of efficient sampling from the hard-core and Potts models from statistical physics. On certain families of graphs, phase transitions in the underlying physics model are linked to changes in the performance of some sampling algorithms, including Markov chains. We develop new sampling and counting algorithms that exploit the phase transition phenomenon and work efficiently on lattices (and bipartite expander graphs) at sufficiently low temperatures in the phase coexistence regime. Our algorithms are based on Pirogov-Sinai theory and the cluster expansion, classical tools from statistical physics. Joint work with Tyler Helmuth and Guus Regts.

Biography:
Will Perkins is an assistant professor in the Department of Mathematics, Statistics, and Computer Science at the University of Illinois at Chicago. His research interests are in probability, combinatorics, and algorithms. He received his PhD in 2011 from New York University, then was a postdoc at Georgia Tech and faculty at the University of Birmingham before moving to UIC in 2018.

MIT Statistics and Data Science Center host guest lecturers from around the world in this weekly seminar.