@inproceedings{befb358275fb4f859b8cdeea18044ea4,
title = "Algorithms for the ferromagnetic Potts model on expanders",
abstract = "We give algorithms for approximating the partition function of the ferromagnetic Potts model on d-regular expanding graphs. We require much weaker expansion than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models, using extremal graph theory and applications of Karger's algorithm to counting cuts that may be of independent interest. It is \#BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of \#BIS are rare. We believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.",
keywords = "approximate counting, approximate sampling, expander graphs, Potts model, random cluster model",
author = "Charlie Carlson and Ewan Davies and Nicolas Fraiman and Alexandra Kolla and Aditya Potukuchi and Corrine Yap",
note = "Publisher Copyright: {\textcopyright} 2022 IEEE.; 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 ; Conference date: 31-10-2022 Through 03-11-2022",
year = "2022",
doi = "10.1109/FOCS54457.2022.00040",
language = "English",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "344--355",
booktitle = "Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022",
address = "United States",
}