Rapid mixing from spectral independence beyond the Boolean domain

Abstract

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ALO20]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper $q$-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree $\Delta$ provided $q\geq ({\alpha}^\star+\delta)$ $\Delta$ where $\alpha^\star\approx 1.763$ is the unique solution to $\alpha^\star=\exp(1/\alpha^\star)$ and $\delta>0$ is any constant. This is the first efficient algorithm for sampling proper $q$-colourings in this regime with possibly unbounded $\Delta$. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].

Type
Publication
ACM Transactions on Algorithms
Weiming Feng
Weiming Feng
Junior Fellow

I am a Junior Fellow at the Institute for Theoretical Studies, ETH Zürich. My research interest lies in theoretical computer science. Currently, I focus on sampling and counting algorithms.

Heng Guo
Heng Guo
Reader

I am a reader in algorithms and complexity in the School of informatics, University of Edinburgh. My research focuses on algorithms from a complexity perspective.

Yitong Yin
Yitong Yin
Professor

I am a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. I am interested in Theoretical Computer Science.

Chihao Zhang
Chihao Zhang
Associate Professor

I am an Associate Professor in John Hopcroft Center for Computer Science at Shanghai Jiao Tong University since 2018. I work in the area of theoretical computer science.