Fast sampling via spectral independence beyond bounded-degree graphs

Spectral independence is a recently-developed framework for obtaining sharp bounds on the convergence time of the classical Glauber dynamics. This new framework has yielded optimal O(n logn) sampling algorithms on bounded-degree graphs for a large class of problems throughout the so-called uniqueness regime, including, for example, the problems of sampling independent sets, matchings, and Ising-model configurations.

In this talk, we will discuss how to relax the bounded-degree assumption that has so far been crucial in establishing and applying spectral independence. Our method generalises previous analyses that applied only to bounded-degree graphs and yields tight algorithmic results for sparse graphs satisfying mild assumptions. As the main application of our techniques, we consider the random graph G(n,d/n), where the previously known algorithms run in time n^{O(log d)} or applied only to large d. We refine these algorithmic bounds significantly, and develop fast n^{1+o(1)} algorithms that apply to all d, based on Glauber dynamics.

Joint work with Ivona Bezakova, Leslie Ann Goldberg, and Daniel Stefankovic.