Computational phase transition and MCMC algorithms
This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model). The computational problem is to sample from the equilibrium distribution of the model or equivalently approximate the corresponding normalizing factor known as the partition function. We show that when correlations die off on the infinite D-regular tree then the Gibbs sampler has optimal mixing time of O(nlogn) on any graph of maximum degree D, whereas when the correlations persist (in the limit) then the sampling/counting problem are NP-hard to approximate. The Gibbs sampler is a simple Markov Chain Monte Carlo (MCMC) algorithm. Key to these mixing results are a new technique known as spectral independence which considers the pairwise influence of vertices. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms.
Eric Vigoda is a Professor of Computer Science at the University of California, Santa Barbara since 2021. Previously, he was on the faculty at Georgia Tech and the University of Chicago. Vigoda completed his PhD in Computer Science from UC Berkeley in 1999. With Mark Jerrum and Alistair Sinclair, they won a Fulkerson prize for their work on approximating the permanent of a non-negative matrix. He is a Fellow of the American Mathematical Society.