Projects per year
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan ) 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.
|Number of pages||33|
|Journal||ACM Transactions on Algorithms|
|Early online date||27 Apr 2022|
|Publication status||Published - 11 Oct 2022|
- graph colouring
- Markov chain Monte Carlo
- spectral independence
FingerprintDive into the research topics of 'Rapid Mixing from Spectral Independence beyond the Boolean Domain'. Together they form a unique fingerprint.
- 1 Active
New Approaches to Counting and Sampling
1/01/21 → 31/12/25