Algorithms for #BIS-hard problems on expander graphs

Matthew Jenssen; Peter Keevash; Will Perkins

doi:10.1137/1.9781611975482.135

Algorithms for #BIS-hard problems on expander graphs

Matthew Jenssen, Peter Keevash, Will Perkins

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Citations (Scopus)

253 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 language	English
Title of host publication	Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms
Editors	Timothy M. Chan
Publisher	Society for Industrial and Applied Mathematics (SIAM)
Pages	2235-2247
Number of pages	13
ISBN (Electronic)	978-1-61197-548-2
DOIs	https://doi.org/10.1137/1.9781611975482.135
Publication status	Published - 9 Jan 2019

Publication series

Name	Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Access to Document

10.1137/1.9781611975482.135Licence: None: All rights reserved

Jenssen_et_al_Algorithms_for_#BIS-hard_problems_Proceedings_of_the_thirtieth_annual_ACM-SIAM_symposium_on_discrete_algorithms_2019
First Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms in 2019, published by the Society for Industrial and Applied Mathematics (SIAM). Copyright © 2019 by SIAM 2235 Unauthorized reproduction of this article is prohibited.
Final published version, 538 KBLicence: None: All rights reserved

https://epubs.siam.org/doi/10.1137/1.9781611975482.135Licence: None: All rights reserved

Cite this

Jenssen, M., Keevash, P., & Perkins, W. (2019). Algorithms for #BIS-hard problems on expander graphs. In T. M. Chan (Ed.), Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms (pp. 2235-2247). (Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611975482.135

@inproceedings{47ea7234bdc54ba5bb8af6b68413c3e7,

title = "Algorithms for #BIS-hard problems on expander graphs",

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.",

author = "Matthew Jenssen and Peter Keevash and Will Perkins",

year = "2019",

month = jan,

day = "9",

doi = "10.1137/1.9781611975482.135",

language = "English",

series = "Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

pages = "2235--2247",

editor = "Chan, {Timothy M.}",

booktitle = "Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms",

}

Jenssen, M, Keevash, P & Perkins, W 2019, Algorithms for #BIS-hard problems on expander graphs. in TM Chan (ed.), Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms. Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics (SIAM), pp. 2235-2247. https://doi.org/10.1137/1.9781611975482.135

Algorithms for #BIS-hard problems on expander graphs. / Jenssen, Matthew; Keevash, Peter; Perkins, Will.
Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms. ed. / Timothy M. Chan. Society for Industrial and Applied Mathematics (SIAM), 2019. p. 2235-2247 (Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Algorithms for #BIS-hard problems on expander graphs

AU - Jenssen, Matthew

AU - Keevash, Peter

AU - Perkins, Will

PY - 2019/1/9

Y1 - 2019/1/9

N2 - 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.

AB - 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.

U2 - 10.1137/1.9781611975482.135

DO - 10.1137/1.9781611975482.135

M3 - Conference contribution

T3 - Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 2235

EP - 2247

BT - Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms

A2 - Chan, Timothy M.

PB - Society for Industrial and Applied Mathematics (SIAM)

ER -

Jenssen M, Keevash P, Perkins W. Algorithms for #BIS-hard problems on expander graphs. In Chan TM, editor, Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics (SIAM). 2019. p. 2235-2247. (Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms). doi: 10.1137/1.9781611975482.135

Algorithms for #BIS-hard problems on expander graphs

Abstract

Publication series

Access to Document

Fingerprint

Cite this