Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
| Autor: | Kuikui Liu, Nima Anari, Shayan Oveis Gharan |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
General Computer Science Distribution (number theory) General Mathematics 0102 computer and information sciences 01 natural sciences Matrix (mathematics) symbols.namesake Simplicial complex Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) 0101 mathematics Computer Science::Distributed Parallel and Cluster Computing Eigenvalues and eigenvectors Independence (probability theory) Mathematics Discrete mathematics Partition function (quantum field theory) 010102 general mathematics Markov chain Monte Carlo Conditional probability distribution 010201 computation theory & mathematics Independent set Bounded function symbols Probability distribution Pairwise comparison Glauber |
| Zdroj: | FOCS |
| DOI: | 10.1109/focs46700.2020.00125 |
| Popis: | We say a probability distribution $\mu$ is spectrally independent if an associated correlation 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 \cite{KM17,DK17,KO18,AL19}, 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 \cite{Wei06} for estimating the hardcore partition function, also answering a long-standing open problem of mixing time of Glauber dynamics \cite{LV97,LV99,DG00,Vig01,EHSVY16}. Comment: Fixed a bug in the decoupling lemma of section 4, and in the proof of Theorem 3.1 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|