Optimal Mixing Via Spectral Independence: Sampling Independent Sets And Colorings

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.