Approximate Counting for Spin Systems in Sub-Quadratic Time

Konrad Anand, Weiming Feng, Graham Freifeld +2

We present two randomised approximate counting algorithms with $\tilde{O}(n^{2-c}/{\epsilon }^2)$ running time for some constant $c>0$ and accuracy $\epsilon$: (1) for the h…