Fetching the paper…
Reading the bibliography…
Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model.
L. G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM Journal on Computing
1979
Earlier work this paper cites.
N. G. de Bruijn. Asymptotic Methods in Analysis
1981
Earlier work this paper cites.
F. P. Kelly. Stochastic Models of Computer Communication Systems. Journal of the Royal Statistical Society. Series B (Methodological)
1985
Earlier work this paper cites.
H.-O. Georgii. Gibbs Measures and Phase Transitions
1988
Earlier work this paper cites.
M. Jerrum and A. Sinclair. Polynomial-time Approximation Algorithms for the Ising Model. SIAM Journal on Computing
1993
Earlier work this paper cites.
S. Janson. Random Regular Graphs: Asymptotic Distributions and Contiguity. Combinatorics, Probability & Computing
1995
Earlier work this paper cites.
M. Molloy, H. Robalewska, R. W. Robinson, and N. C. Wormald. 1-Factorizations of random regular graphs. Random Structures and Algorithms
1997
Earlier work this paper cites.
N.C. Wormald. Models of random regular graphs. In Surveys in Combinatorics, 1999 (Canterbury)
1999
Earlier work this paper cites.
C. Greenhill. The complexity of counting colorings and independent sets in sparse graphs and hypergraphs. Computational Complexity
2000
Earlier work this paper cites.
S. Janson, T. Łuczak, and A. Rucinski. Random Graphs
2000
Earlier work this paper cites.
M. Dyer, A. M. Frieze, and M. Jerrum. On counting independent sets in sparse graphs. SIAM Journal on Computing
2002
Earlier work this paper cites.
L.A. Goldberg, M. Jerrum and M. Paterson. The computational complexity of two-state spin systems. Random Structures and Algorithms
2003
Cited alongside, same era.
M. Talagrand. Spin Glasses: A Challenge for Mathematicians
2003
Cited alongside, same era.
D. Achlioptas and Y. Peres. The threshold for random k-SAT is 2 k log 2 − O ( k ) 2^{k}\log{2}-O(k) . Journal of the AMS
2004
Cited alongside, same era.
F. Martinelli, A. Sinclair, and D. Weitz. Glauber Dynamics on Trees: Boundary Conditions and Mixing Time. Communications in Mathematical Physics
2004
Cited alongside, same era.
E. Mossel. Survey: Information flow on trees. In Graphs, Morphisms, and Statistical Physics
2004
Cited alongside, same era.
2011
Later among the works it cites.
V. Beffara and H. Duminil-Copin. The self-dual point of the two-dimensional random cluster model is critical for q ≥ 1 q\geq 1 . Probability Theory and Related Fields
2012
Closest in time.
2012
Closest in time.
A. Dembo, A. Montanari, and N. Sun. Factor models on locally tree-like graphs. The Annals of Probability
2013
Closest in time.
L. Li, P. Lu, Y. Yin. Correlation Decay up to Uniqueness in Spin Systems. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
2005
Cited alongside, same era.
Counting independent sets up to the tree threshold
D. Weitz · 2006
Cited alongside, same era.
F. Martinelli, A. Sinclair, and D. Weitz. Fast Mixing for Independent Sets, Colorings, and Other Models on Trees. Random Structures and Algorithms
2007
Cited alongside, same era.
M. Mezard and A. Montanari. Information, Physics, and Computation
2009
Cited alongside, same era.
E. Mossel, D. Weitz, and N. Wormald. On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields
2009
Cited alongside, same era.
A. Sly. Computational Transition at the Uniqueness Threshold. In Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science
2010
Cited alongside, same era.
2013
Closest in time.
R. Restrepo, J. Shin, P. Tetali, E. Vigoda, and L. Yang. Improved mixing condition on the grid for counting and sampling independent sets. Probability Theory and Related Fields
2013
Closest in time.
J.-Y. Cai, A. Galanis, L. A. Goldberg, H. Guo, M. Jerrum, D. Štefankovič, and E. Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. In Proceedings of the 18th International Workshop on Randomization and Computation
2014
Closest in time.
A. Galanis, Q. Ge, D. Štefankovič, E. Vigoda, and L. Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model. Random Structures & Algorithms
2014
Closest in time.
A. Galanis, D. Štefankovič, and E. Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC)
2014
Closest in time.
A. Sinclair, P. Srivastava, and M. Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. Journal of Statistical Physics
2014
Closest in time.
A. Sly and N. Sun. The Computational Hardness of Counting in Two-Spin Models on d-Regular Graphs. The Annals of Probability
2014
Closest in time.