Algorithms for #BIS-hard problems on expander graphs

Author: 

Jenssen, M
Keevash, P
Perkins, W

Publication Date: 

6 January 2019

Journal: 

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Last Updated: 

2021-06-21T08:32:10.927+01:00

Volume: 

abs/1807.04804

DOI: 

10.1137/1.9781611975482.135

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

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article

ISBN-13: 

9781611975482