Seminar-Eric Vigoda

Event Date: 

Wednesday, December 1, 2021 - 3:30pm to 4:30pm

Event Location: 

  • Broida Hall 1640

Title: Computational phase transition and MCMC algorithms

Speaker: Eric Vigoda, UCSB Computer Science

Abstract: This talk will give an overview of a new technique known as spectral independence for establishing rapid mixing results for Markov Chain Monte Carlo (MCMC) algorithms. Spectral independence considers the pairwise influence of vertices in an undirected graphical model or spin system. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms. This yields a dramatic computational phase transition for approximating the partition function in several settings, including the statistical physics Ising model and the combinatorial hard-core model on weighted independent sets. The talk is based on joint works with Zongchen Chen (MIT) and Kuikui Liu (Washington).