Algorithmic Pirogov-Sinai Theory

2019. 04. 11. 16:15
Tyler Helmuth (Bristol)

What does a random independent set look like? This is an important problem at the intersection of probability theory, statistical mechanics, and theoretical computer science. I will introduce this problem, also known as the hard-core model, and explain various ways in which the question can be answered. In particular, I will describe a recent algorithm for producing approximate samples of high-density independent sets on lattices. This is the first known algorithm in the high-density regime, and standard algorithms, like MCMC using Glauber dynamics, are known to fail. 

Based on joint work with Will Perkins and Guus Regts.