Rapid mixing from spectral independence beyond the Boolean domain

Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 푞-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided 푞 ≥ (α* + δ)Δ where α* ≈ 1.763 is the unique solution to α* = exp(1/α*) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper 푞-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [GMP05].
Original languageEnglish
Title of host publicationProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21)
PublisherACM
Pages1558 – 1577
Number of pages20
ISBN (Print)9781611976465
Publication statusPublished - 10 Jan 2021
EventACM-SIAM Symposium on Discrete Algorithms - Virtual event
Duration: 10 Jan 202113 Jan 2021
https://www.siam.org/conferences/cm/conference/soda21

Symposium

SymposiumACM-SIAM Symposium on Discrete Algorithms
Abbreviated titleSODA 21
CityVirtual event
Period10/01/2113/01/21
Internet address

Fingerprint

Dive into the research topics of 'Rapid mixing from spectral independence beyond the Boolean domain'. Together they form a unique fingerprint.

Cite this