EUVIMEDEUVIMED entdecken
Crossref

Spectral Independence via Stability and Applications to Holant-Type Problems

Zongchen Chen, Kuikui Liu, Eric Vigoda

TheoretiCS · 2024

DOI: 10.46298/theoretics.24.16 ↗

Kurz gefasst

Fachartikel in der Zeitschrift TheoretiCS, 2024. Verfasst von Zongchen Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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, we obtain optimal $O(n\log n)$ mixing time bounds for the single-site update Markov chain known as the Glauber dynamics. Our result significantly improves the running time guarantees obtained via the polynomial interpolation method of Barvinok (2017), refined by Patel and Regts (2017). There are a variety of applications of our results. In this paper, we focus on Holant-type (i.e., edge-coloring) problems, including weighted edge covers and weighted even subgraphs. For the weighted edge cover problem (and several natural generalizations) we obtain an $O(n\log{n})$ sampling algorithm on bounded-degree graphs. The even subgraphs problem corresponds to the high-temperature expansion of the ferromagnetic Ising model. We obtain an $O(n\log{n})$ sampling algorithm for the ferromagnetic Ising model with a nonzero external field on bounded-degree graphs, which improves upon the classical result of Jerrum and Sinclair (1993) for this class of graphs. We obtain further applications to antiferromagnetic two-spin models on line graphs, weighted graph homomorphisms, tensor networks, and more.

Zitieren

APA

Chen, Z., Liu, K., & Vigoda, E. (2024). Spectral Independence via Stability and Applications to Holant-Type Problems. TheoretiCS. https://doi.org/10.46298/theoretics.24.16

Vancouver

Chen Z, Liu K, Vigoda E. Spectral Independence via Stability and Applications to Holant-Type Problems. TheoretiCS. 2024. doi:10.46298/theoretics.24.16

BibTeX
@article{Chen2024,
  author = {Chen, Zongchen and Liu, Kuikui and Vigoda, Eric},
  title = {Spectral Independence via Stability and Applications to Holant-Type Problems},
  journal = {TheoretiCS},
  year = {2024},
  doi = {10.46298/theoretics.24.16}
}
Kostenlos starten →