Projects per year
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].
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 language | English |
---|---|
Title of host publication | Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21) |
Publisher | ACM |
Pages | 1558 – 1577 |
Number of pages | 20 |
ISBN (Print) | 9781611976465 |
Publication status | Published - 10 Jan 2021 |
Event | ACM-SIAM Symposium on Discrete Algorithms - Virtual event Duration: 10 Jan 2021 → 13 Jan 2021 https://www.siam.org/conferences/cm/conference/soda21 |
Symposium
Symposium | ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Abbreviated title | SODA 21 |
City | Virtual event |
Period | 10/01/21 → 13/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.Projects
- 1 Active
-
New Approaches to Counting and Sampling
Guo, H. (Principal Investigator)
1/01/21 → 31/12/25
Project: Research