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

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].