Asymptotically faster algorithm for counting self-avoiding walks and self-avoiding polygons

Abstract

We give an algorithm for counting self-avoiding walks or self-avoiding polygons that runs in time $\exp (C\sqrt{n\log n})$ on 2-dimensional lattices and time $\exp (C_d{n}^{(d-1)/d}\log n)$ on $d$-dimensional lattices for $d>2$.

Added citations and rewrote some places for clarity