Full Name
Eric Vigoda
Company
UC Santa Barbara
Abstract
Anari, Liu, and Oveis Gharan (2020) introduced a new technique called spectral independence for bounding the mixing rate of the Gibbs sampler. In joint work with Z. Chen and K. Liu, we proved that spectral independence implies optimal mixing time bounds for the Gibbs sampler for graphical models on constant degree graphs. I'll illustrate these results by highlighting a beautiful computational phase transition for sampling (weighted) independent sets. I'll also discuss more recent work (with C. Carlson) on sampling colorings using a flip dynamics.
Eric Vigoda