Algorithmic Pirogov-sinai theory

Tyler Helmuth, Will Perkins, Guus Regts

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

9 Citations (Scopus)
179 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery (ACM)
Pages1009-1020
Number of pages12
ISBN (Electronic)9781450367059
DOIs
Publication statusPublished - 23 Jun 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: 23 Jun 201926 Jun 2019

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
CountryUnited States
CityPhoenix
Period23/06/1926/06/19

Keywords

  • Approximate counting algorithms
  • Hard-core model
  • Pirogov-Sinai theory
  • Potts model
  • Sampling algorithms
  • Statistical physics

Fingerprint Dive into the research topics of 'Algorithmic Pirogov-sinai theory'. Together they form a unique fingerprint.

Cite this