Fetching the paper…
Reading the bibliography…
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every $\Delta$-regular bipartite graph if $\Delta\ge 53$.
Phase diagrams of classical lattice systems
S. A. Pirogov and Ya. G. Sinai · 1975
Earlier work this paper cites.
Phase diagrams of classical lattice systems continuation
S. A. Pirogov and Ya. G. Sinai · 1976
Earlier work this paper cites.
Asymptotically optimal switching circuits
Leonid A. Bassalygo · 1981
Earlier work this paper cites.
Cluster expansion for abstract polymer models
R. Kotecký and D. Preiss · 1986
Earlier work this paper cites.
A very simple algorithm for estimating the number of k-colorings of a low-degree graph
Mark Jerrum · 1995
Earlier work this paper cites.
Path coupling: A technique for proving rapid mixing in Markov chains
Russ Bubley and Martin Dyer · 1997
Earlier work this paper cites.
1-factorizationss of random regular graphs
M. S. O. Molloy, H. Robalewska, R. W. Robinson, and N. C. Wormald · 1997
Earlier work this paper cites.
On approximately counting colorings of small degree graphs
Russ Bubley, Martin Dyer, Catherine Greenhill, and Mark Jerrum · 1999
Earlier work this paper cites.
Improved bounds for sampling colorings
Eric Vigoda · 2000
Earlier work this paper cites.
On counting independent sets in sparse graphs
Martin E. Dyer, Alan M. Frieze, and Mark Jerrum · 2002
Earlier work this paper cites.
Randomly coloring graphs with lower bounds on girth and maximum degree
Martin Dyer and Alan Frieze · 2003
Earlier work this paper cites.
Randomly coloring graphs of girth at least five
Thomas P Hayes · 2003
Earlier work this paper cites.
A non-markovian coupling for randomly sampling colorings
Thomas P Hayes and Eric Vigoda · 2003
Earlier work this paper cites.
The relative complexity of approximate counting problems
Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum · 2004
Earlier work this paper cites.
The Glauber dynamics on colorings of a graph with high girth and maximum degree
Michael Molloy · 2004
Earlier work this paper cites.
Randomly coloring sparse random graphs with fewer colors than the maximum degree
Martin Dyer, Abraham D Flaxman, Alan M Frieze, and Eric Vigoda · 2006
Cited alongside, same era.
Coupling with the stationary distribution and improved sampling for colorings and independent sets
Thomas P Hayes and Eric Vigoda · 2006
Cited alongside, same era.
Counting independent sets up to the tree threshold
Dror Weitz · 2006
Cited alongside, same era.
On the hardness of sampling independent sets beyond the tree threshold
Elchanan Mossel, Dror Weitz, and Nicolas Wormald · 2009
Cited alongside, same era.
An approximation trichotomy for boolean #CSP
Martin E. Dyer, Leslie Ann Goldberg, and Mark Jerrum · 2010
Cited alongside, same era.
Computational transition at the uniqueness threshold
Allan Sly · 2010
Cited alongside, same era.
Combinatorics and Complexity of Partition Functions
Alexander I. Barvinok · 2016
Later among the works it cites.
Computing the partition function for graph homomorphisms with multiplicities
Alexander I. Barvinok and Pablo Soberón · 2016
Later among the works it cites.
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda · 2016
Later among the works it cites.
Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
Andreas Galanis, Daniel Štefankovič, and Eric Vigoda · 2016
Later among the works it cites.
Ferromagnetic potts model: Refined #BIS-hardness and related results
Andreas Galanis, Daniel Štefankovič, Eric Vigoda, and Linji Yang · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Approximating the partition function of the ferromagnetic potts model
Leslie Ann Goldberg and Mark Jerrum · 2012
Cited alongside, same era.
Correlation decay and deterministic FPTAS for counting colorings of a graph
David Gamarnik and Dmitriy Katz · 2012
Cited alongside, same era.
The computational hardness of counting in two-spin models on d d -regular graphs
Allan Sly and Nike Sun · 2012
Cited alongside, same era.
Left and right convergence of graphs with bounded degree
Christian Borgs, Jennifer T. Chayes, Jeff Kahn, and László Lovász · 2013
Cited alongside, same era.
The expressibility of functions on the Boolean domain, with applications to counting CSPs
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, and Colin McQuillan · 2013
Cited alongside, same era.
Randomly coloring constant degree graphs
Martin Dyer, Alan Frieze, Thomas P Hayes, and Eric Vigoda · 2013
Cited alongside, same era.
Sacha Friedli and Yvan Velenik · 2017
Later among the works it cites.
Approximating partition functions of bounded-degree boolean counting constraint satisfaction problems
Andreas Galanis, Leslie Ann Goldberg, and Kuan Yang · 2017
Later among the works it cites.
An FPTAS for counting proper four-colorings on cubic graphs
Pinyan Lu, Kuan Yang, Chihao Zhang, and Minshen Zhu · 2017
Later among the works it cites.
Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis
Michael Mitzenmacher and Eli Upfal · 2017
Later among the works it cites.
Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
Viresh Patel and Guus Regts · 2017
Later among the works it cites.
Counting hypergraph colourings in the local lemma regime
Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang · 2018
Later among the works it cites.
Algorithmic Pirogov-Sinai theory
Tyler Helmuth, Will Perkins, and Guus Regts · 2018
Later among the works it cites.
Improved bounds for randomly sampling colorings via linear programming
Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, and Luke Postle · 2019
Closest in time.
Algorithms for #BIS-hard problems on expander graphs
Matthew Jenssen, Peter Keevash, and Will Perkins · 2019
Closest in time.