  We present two randomised approximate counting algorithms with
$\widetilde{O}(n^{2-c}/\varepsilon^2)$ running time for some constant $c>0$ and
accuracy $\varepsilon$:
  (1) for the hard-core model with fugacity $\lambda$ on graphs with maximum
degree $\Delta$ when $\lambda=O(\Delta^{-1.5-c_1})$ where $c_1=c/(2-2c)$;
  (2) for spin systems with strong spatial mixing (SSM) on planar graphs with
quadratic growth, such as $\mathbb{Z}^2$.
  For the hard-core model, Weitz's algorithm (STOC, 2006) achieves
sub-quadratic running time when correlation decays faster than the
neighbourhood growth, namely when $\lambda = o(\Delta^{-2})$. Our first
algorithm does not require this property and extends the range where
sub-quadratic algorithms exist.
  Our second algorithm appears to be the first to achieve sub-quadratic running
time up to the SSM threshold, albeit on a restricted family of graphs. It also
extends to (not necessarily planar) graphs with polynomial growth, such as
$\mathbb{Z}^d$, but with a running time of the form
$\widetilde{O}\left(n^2\varepsilon^{-2}/2^{c(\log n)^{1/d}}\right)$ where $d$
is the exponent of the polynomial growth and $c>0$ is some constant.
