Fetching the paper…
Reading the bibliography…
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.
General properties of polymer systems
C. Gruber and H. Kunz · 1971
Earlier work this paper cites.
Phase diagrams of classical lattice systems
S. A. Pirogov and Y. G. Sinai · 1975
Earlier work this paper cites.
Asymptotically optimal switching circuits
L. Bassalygo · 1981
Earlier work this paper cites.
Explicit concentrators from generalized n-gons
R. M. Tanner · 1984
Earlier work this paper cites.
Stochastic models of computer communication systems
F. P. Kelly · 1985
Earlier work this paper cites.
Eigenvalues and expanders
N. Alon · 1986
Earlier work this paper cites.
Cluster expansion for abstract polymer models
R. Kotecký and D. Preiss · 1986
Earlier work this paper cites.
Nonuniversal critical dynamics in Monte Carlo simulations
R. H. Swendsen and J.-S. Wang · 1987
Earlier work this paper cites.
Polynomial-time approximation algorithms for the Ising model
M. Jerrum and A. Sinclair · 1993
Earlier work this paper cites.
Estimates of semi-invariants for the Ising model at low temperatures
R. Dobrushin · 1996
Earlier work this paper cites.
Sampling spin configurations of an Ising system
D. Randall and D. Wilson · 1999
Earlier work this paper cites.
A proof of Alon’s second eigenvalue conjecture
J. Friedman · 2003
Earlier work this paper cites.
The relative complexity of approximate counting problems
M. Dyer, L. A. Goldberg, C. Greenhill, and M. Jerrum · 2004
Earlier work this paper cites.
On phase transition in the hard-core model on ℤ d \mathbb{Z}^{d}
D. Galvin and J. Kahn · 2004
Earlier work this paper cites.
The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
A. D. Scott and A. D. Sokal · 2005
Earlier work this paper cites.
Expander graphs and their applications
S. Hoory, N. Linial, and A. Wigderson · 2006
Earlier work this paper cites.
Counting independent sets up to the tree threshold
D. Weitz · 2006
Cited alongside, same era.
Unique games on expanding constraint graphs are easy
S. Arora, S. A. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. K. Vishnoi · 2008
Cited alongside, same era.
Computing the Tutte polynomial in vertex-exponential time
A. Björklund, T. Husfeldt, P. Kaski, and M. Koivisto · 2008
Cited alongside, same era.
On the hardness of sampling independent sets beyond the tree threshold
E. Mossel, D. Weitz, and N. Wormald · 2009
Cited alongside, same era.
How to play unique games on expanders
K. Makarychev and Y. Makarychev · 2010
Cited alongside, same era.
Computational transition at the uniqueness threshold
A. Sly · 2010
Cited alongside, same era.
Combinatorics and Complexity of Partition Functions
A. Barvinok · 2017
Later among the works it cites.
Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
V. Patel and G. Regts · 2017
Later among the works it cites.
Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
A. Blanca, A. Galanis, L. A. Goldberg, D. Stefankovic, E. Vigoda, and K. Yang · 2018
Closest in time.
Spectral gap in random bipartite biregular graphs and applications
G. Brito, I. Dumitriu, and K. D. Harris · 2018
Closest in time.
Random cluster dynamics for the Ising model is rapidly mixing
H. Guo and M. Jerrum · 2018
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The complexity of approximately counting stable matchings
P. Chebolu, L. A. Goldberg, and R. Martin · 2012
Cited alongside, same era.
Approximating the partition function of the ferromagnetic Potts model
L. A. Goldberg and M. Jerrum · 2012
Cited alongside, same era.
The replica symmetric solution for Potts models on d-regular graphs
A. Dembo, A. Montanari, A. Sly, and N. Sun · 2014
Cited alongside, same era.
Counting in two-spin models on d-regular graphs
A. Sly and N. Sun · 2014
Cited alongside, same era.
FPTAS for #BIS with degree bounds on one side
J. Liu and P. Lu · 2015
Cited alongside, same era.
Computing the permanent of (some) complex matrices
A. Barvinok · 2016
Cited alongside, same era.
R. Peled and Y. Spinka · 2018
Closest in time.
Weighted counting of solutions to sparse systems of equations
A. Barvinok and G. Regts · 2019
Closest in time.
Zeros and approximations of Holant polynomials on the complex plane
K. Casel, P. Fischbeck, T. Friedrich, A. Göbel, and J. Lagodzinski · 2019
Closest in time.
Fast algorithms at low temperatures via Markov chains
Z. Chen, A. Galanis, L. A. Goldberg, W. Perkins, J. Stewart, and E. Vigoda · 2019
Closest in time.
Algorithmic Pirogov-Sinai theory
T. Helmuth, W. Perkins, and G. Regts · 2019
Closest in time.
Algorithms for #BIS-hard problems on expander graphs
M. Jenssen, P. Keevash, and W. Perkins · 2019
Closest in time.
Counting independent sets and colorings on random regular bipartite graphs
C. Liao, J. Lin, P. Lu, and Z. Mao · 2019
Closest in time.
Computing the number of induced copies of a fixed graph in a bounded degree graph
V. Patel and G. Regts · 2019
Closest in time.
Spectral independence in high-dimensional expanders and applications to the hardcore model
N. Anari, K. Liu, and S. O. Gharan · 2020
Closest in time.
Counting independent sets in unbalanced bipartite graphs
S. Cannon and W. Perkins · 2020
Closest in time.