[2204.01923] Algorithms for the ferromagnetic Potts model on expanders
source link: https://arxiv.org/abs/2204.01923
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 5 Apr 2022 (v1), last revised 18 Sep 2022 (this version, v2)]
Algorithms for the ferromagnetic Potts model on expanders
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.
| Comments: | 27 pages; added Theorem 2 as separate statement; to appear in FOCS 2022 |
| Subjects: | Data Structures and Algorithms (cs.DS); Discrete Mathematics (cs.DM); Combinatorics (math.CO) |
| Cite as: | arXiv:2204.01923 [cs.DS] |
| (or arXiv:2204.01923v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2204.01923 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK