Author
Jenssen, M
Keevash, P
Perkins, W
Journal title
SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms
DOI
10.1137/1.9781611975482.135
Last updated
2024-03-24T06:08:24.363+00:00
Page
2235-2247
Abstract
We give an FPTAS and an efficient sampling algorithm for the high-fugacity hard-core model on bounded-degree bipartite expander graphs and the low-temperature ferromagnetic Potts model on bounded-degree expander graphs. The results apply, for example, to random (bipartite) Δ-regular graphs, for which no efficient algorithms were known for these problems (with the exception of the Ising model) in the non-uniqueness regime of the infinite Δ-regular tree.
Symplectic ID
870560
Favourite
Off
Publication type
Journal Article
ISBN-13
9781611975482
Publication date
06 Jan 2019
Please contact us with feedback and comments about this page. Created on 16 Jul 2018 - 15:53.