Algorithmic Pirogov-Sinai theory

• 成果类型: Article
• 署名作者: Helmuth, Tyler; Perkins, Will; Regts, Guus
• 署名单位: University of Bristol; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; University of Amsterdam
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-019-00928-y
• 发表日期: 2020
• 页码: 851-895
• 关键词: time approximation algorithms; random-cluster dynamics; number-bis-hardness; phase-diagrams; partition-function; potts-model; ising-model; core model; generation; systems

摘要

We develop an efficient algorithmic approach for approximate counting and sampling in the low-temperature regime of a broad class of statistical physics models on finite subsets of the lattice Zd and on the torus (Z/nZ)d. Our approach is based on combining contour representations from Pirogov-Sinai theory with Barvinok's approach to approximate counting using truncated Taylor series. Some consequences of our main results include an FPTAS for approximating the partition function of the hard-core model at sufficiently high fugacity on subsets of Zd with appropriate boundary conditions and an efficient sampling algorithm for the ferromagnetic Potts model on the discrete torus (Z/nZ)d at sufficiently low temperature.