REVIEW 1 cited by
Algorithms for #BIS-hard problems on expander graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Algorithms for #BIS-hard problems on expander graphs
read the original 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) $\Delta$-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 $\Delta$-regular tree. We also find efficient counting and sampling algorithms for proper $q$-colorings of random $\Delta$-regular bipartite graphs when $q$ is sufficiently small as a function of $\Delta$.
Forward citations
Cited by 1 Pith paper
-
Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
A cluster-expansion FPTAS for the partition function and an approximate sampler for weakly-interacting quantum spin systems at arbitrary temperature are claimed, but a key bound in the proof fails.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.