Abstract | ||
---|---|---|
This paper formalizes connections between stability of polynomials and convergence rates of Markov Chain Monte Carlo (MCMC) algorithms. We prove that if a (multivariate) partition function is nonzero in a region around a real point $\lambda$ then spectral independence holds at $\lambda$. As a consequence, for Holant-type problems (e.g., spin systems) on bounded-degree graphs,... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00023 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Computer science,Interpolation,Monte Carlo methods,Tensors,Markov processes,Stability analysis,Partitioning algorithms | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Zongchen Chen | 1 | 2 | 6.13 |
Kuikui Liu | 2 | 2 | 2.07 |
Eric Vigoda | 3 | 747 | 76.55 |