May 12, 2023, ESB 2001

Markov Chain Monte Carlo (MCMC) algorithms are an important tool for sampling from high-dimensional distributions, such as the equilibrium distribution of (undirected) graphical models. The Gibbs sampler is the simplest example of an MCMC algorithm; its transitions update the configuration at a randomly chosen coordinate/vertex in each step. We prove that a new technique called spectral independence implies optimal mixing bounds for the Gibbs sampler. We'll discuss these results in the framework of independent sets of a graph, and explore how they connect to statistical physics phase transitions. This is joint work with Zongchen Chen (MIT) and Kuikui Liu (MIT).

Eric Vigoda joined UCSB Computer Science in 2021. Previously, he was a faculty member at Georgia Tech since 2004, and he received his PhD from UC Berkeley in 1999. His work with Mark Jerrum and Alistair Sinclair presenting a MCMC algorithm to approximate the permanent won a Fulkerson Prize. He is a Fellow of the American Mathematical Society (AMS).