EUVIMEDEUVIMED entdecken
Crossref

Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model

Nima Anari, Kuikui Liu, Shayan Oveis Gharan

SIAM Journal on Computing · 2024-12 · 53 (6) · FOCS20-1-FOCS20-37

DOI: 10.1137/20m1367696 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 12.07.2021. Verfasst von Nima Anari und 2 weiteren Autor:innen. Die Arbeit wurde bisher 22-mal zitiert (Crossref) und nennt 73 Literaturangaben. Gefördert von: Office of Naval Research, National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We say a probability distribution $\mu$ is spectrally independent if an associated pairwise influence matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if $\mu$ is spectrally independent, then the corresponding high-dimensional simplicial complex is a local spectral expander. Using a line of recent works on mixing time of high-dimensional walks on simplicial complexes [T. Kaufman and D. Mass, Proceedings of ITCS, 2017, pp. 4:1–4:27; I. Dinur and T. Kaufman, Proceedings of the IEEE 58th Annual Symposium on Foundations of Computer Science, 2017, pp. 974–985; T. Kaufman and I. Oppenheim, Proceedings of APPROX/RANDOM, 2018, pp. 47:1–47:17; V. L. Alev and L. C. Lau, Proceedings of the 52nd Annual ACM Symposium on Theory of Computing, 2020], this implies that the corresponding Glauber dynamics mixes rapidly and generates (approximate) samples from $\mu$. As an application, we show that natural Glauber dynamics mixes rapidly (in polynomial time) to generate a random independent set from the hardcore model up to the uniqueness threshold. This improves the quasi-polynomial running time of Weitz's deterministic correlation decay algorithm [D. Weitz, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 140–149] for estimating the hardcore partition function, also answering a long-standing open problem of mixing time of Glauber dynamics [M. Luby and E. Vigoda, Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, pp. 682–687; M. Luby and E. Vigoda, Random Structures Algorithms, 15 (1999), pp. 229–241; M. Dyer and C. Greenhill, J. Algorithms, 35 (2000), pp. 17–49; E. Vigoda, Electron. J. Combin., 8 (2001); C. Efthymiou et al., Proceedings of FOCS, 2016, pp. 704–713].

Förderung

  • Office of Naval Research
  • National Science Foundation

Zitieren

APA

Anari, N., Liu, K., & Gharan, S. O. (2024). Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. SIAM Journal on Computing, 53(6), FOCS20-1-FOCS20-37. https://doi.org/10.1137/20m1367696

Vancouver

Anari N, Liu K, Gharan SO. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. SIAM Journal on Computing. 2024;53(6):FOCS20-1-FOCS20-37. doi:10.1137/20m1367696

BibTeX
@article{Anari2024,
  author = {Anari, Nima and Liu, Kuikui and Gharan, Shayan Oveis},
  title = {Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model},
  journal = {SIAM Journal on Computing},
  year = {2024},
  volume = {53},
  number = {6},
  pages = {FOCS20--1--FOCS20--37},
  doi = {10.1137/20m1367696}
}
Kostenlos starten →