# Rapid mixing from spectral independence beyond the Boolean domain

arXiv: https://arxiv.org/abs/2007.08091 · HTML: https://mlsanity.com/paper/2007.08091/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 2 of 2)

- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)

## Abstract (arXiv)

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≥ (α^*+δ)Delta where α^*≈ 1.763 is the unique solution to α^*=exp(1/α^*) and δ>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].