Algorithms for #BIS-hard problems on expander graphs

Matthew Jenssen, Peter Keevash, Will Perkins

Research output: Chapter in Book/Report/Conference proceedingConference contribution

16 Citations (Scopus)
226 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms
EditorsTimothy M. Chan
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages2235-2247
Number of pages13
ISBN (Electronic)978-1-61197-548-2
DOIs
Publication statusPublished - 9 Jan 2019

Publication series

NameProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Fingerprint

Dive into the research topics of 'Algorithms for #BIS-hard problems on expander graphs'. Together they form a unique fingerprint.

Cite this