Approximate Counting for Spin Systems in Sub-Quadratic Time
share
We present two approximate counting algorithms with O(n^2-c/ε^2) running time for some constant c > 0 and accuracy ε: (1) for the hard-core model when strong spatial mixing (SSM) is sufficiently fast; (2) for spin systems with SSM on planar graphs with quadratic growth, such as ℤ^2. The latter algorithm also extends to (not necessarily planar) graphs with polynomial growth, such as ℤ^d, albeit with a running time of the form O(n^2ε^-2/2^c(log n)^1/d) for some constant c > 0 and d being the exponent of the polynomial growth. Our technique utilizes Weitz's self-avoiding walk tree (STOC, 2006) and the recent marginal sampler of Anand and Jerrum (SIAM J. Comput., 2022).
READ FULL TEXT