Spatial mixing and approximation algorithms for graphs with bounded connective constant

Poor man’s Monte Carlo

Hammersley, J. M., and Morton, K. W · 1954

Earlier work this paper cites.

Percolation processes I. Crystals and mazes

Broadbent, S. R., and Hammersley, J. M · 1957

Earlier work this paper cites.

Percolation processes II. The connective constant

Hammersley, J. M · 1957

Earlier work this paper cites.

On the number of self-avoiding walks. II

Kesten, H · 1964

Earlier work this paper cites.

Exact critical point and critical exponents of O ⁡ ( n ) O(n) models in two dimensions

Nienhuis, B · 1982

Earlier work this paper cites.

Random generation of combinatorial structures from a uniform distribution

Jerrum, M., Valiant, L. G., and Vazirani, V. V · 1986

Earlier work this paper cites.

The Ising model and percolation on trees and tree-like graphs

Lyons, R · 1989

Earlier work this paper cites.

Random walks and percolation on trees

Lyons, R · 1990

Earlier work this paper cites.

Upper bounds for the connective constant of self-avoiding walks

Alm, S. E · 1993

Earlier work this paper cites.

Polynomial-time approximation algorithms for the Ising model

Jerrum, M., and Sinclair, A · 1993

Earlier work this paper cites.

The Self-Avoiding Walk

Madras, N., and Slade, G · 1996

Earlier work this paper cites.

Approximately counting up to four

Luby, M., and Vigoda, E · 1997

Cited alongside, same era.

Robust phase transitions for Heisenberg and other models on general trees

Pemantle, R., and Steif, J. E · 1999

Cited alongside, same era.

Improved upper bounds for self-avoiding walks in ℤ d \mathbb{Z}^{d}

Pönitz, A., and Tittmann, P · 2000

Cited alongside, same era.

The computational complexity of two-state spin systems

Goldberg, L. A., Jerrum, M., and Paterson, M · 2003

Cited alongside, same era.

Enumeration of self-avoiding walks on the square lattice

Jensen, I · 2004

Cited alongside, same era.

Survey: Information flow on trees

Mossel, E · 2004

Cited alongside, same era.

Computational transition at the uniqueness threshold

Sly, A · 2010

Later among the works it cites.

The connective constant of the honeycomb lattice equals 2 + 2 \sqrt{2+\sqrt{2}}

Duminil-Copin, H., and Smirnov, S · 2012

Later among the works it cites.

Approximate counting via correlation decay in spin systems

Li, L., Lu, P., and Yin, Y · 2012

Later among the works it cites.

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

Sinclair, A., Srivastava, P., and Thurley, M · 2012

Later among the works it cites.

MCMC sampling colourings and independent sets of 𝒢 ⁡ ( n , d / n ) \mathcal{G}(n,d/n) near the uniqueness threshold

Original

Efthymiou, C · 2013

Closest in time.

Correlation decay up to uniqueness in spin systems