Rapid Mixing from Spectral Independence beyond the Boolean Domain
ACM Transactions on Algorithms · 31.07.2022 · 18 (3) · 1-32
DOI: 10.1145/3531008 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Algorithms, online erschienen am 11.10.2022. Verfasst von Weiming Feng und 3 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 50 Literaturangaben. Gefördert von: NSFC, European Research Council.
Abstract (Originalsprache)
We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [ 4 ]) 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 Δ provided q ≥ ( α * + δ )Δ 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 Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [ 25 ].
Förderung
- NSFC
- European Research Council
Zitieren
APA
Feng, W., Guo, H., Yin, Y., & Zhang, C. (2022). Rapid Mixing from Spectral Independence beyond the Boolean Domain. ACM Transactions on Algorithms, 18(3), 1-32. https://doi.org/10.1145/3531008
Vancouver
Feng W, Guo H, Yin Y, Zhang C. Rapid Mixing from Spectral Independence beyond the Boolean Domain. ACM Transactions on Algorithms. 2022;18(3):1-32. doi:10.1145/3531008
BibTeX
@article{Feng2022,
author = {Feng, Weiming and Guo, Heng and Yin, Yitong and Zhang, Chihao},
title = {Rapid Mixing from Spectral Independence beyond the Boolean Domain},
journal = {ACM Transactions on Algorithms},
year = {2022},
volume = {18},
number = {3},
pages = {1--32},
doi = {10.1145/3531008}
}
EUVIMED