@inproceedings{8a952430cf4a4cec80f05bf020838070,

title = "Algorithmic Pirogov-sinai theory",

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{\textquoteright}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.",

keywords = "Approximate counting algorithms, Hard-core model, Pirogov-Sinai theory, Potts model, Sampling algorithms, Statistical physics",

author = "Tyler Helmuth and Will Perkins and Guus Regts",

year = "2019",

month = jun,

day = "23",

doi = "10.1145/3313276.3316305",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery (ACM)",

pages = "1009--1020",

editor = "Moses Charikar and Edith Cohen",

booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",

address = "United States",

note = "51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

}