Algorithms for #BIS-hard problems on expander graphs

DOI10.1137/1.9781611975482.135zbMath1432.68619arXiv1807.04804OpenAlexW2884258630MaRDI QIDQ5236322

Peter Keevash, Will Perkins, Matthew Jenssen

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.04804

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Algorithmic Pirogov-Sinai theory ⋮ Fast algorithms at low temperatures via Markov chains† ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Independent sets in the hypercube revisited ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ Unnamed Item ⋮ Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs ⋮ Weighted counting of solutions to sparse systems of equations ⋮ Efficient algorithms for approximating quantum partition functions ⋮ Polymer dynamics via cliques: new conditions for approximations

This page was built for publication: Algorithms for #BIS-hard problems on expander graphs