# Eric Vigoda, Computational phase transition and MCMC algorithms

## July 4 Monday @ 4:30 PM - 5:30 PM KST

Room B332, IBS (기초과학연구원)

### Speaker

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 or on weighted independent sets). 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(n \log n)$ 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.

## Details

Date:
July 4 Monday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Room B332