Improved algorithm for counting spanning trees by ${\mathrm{\ell }}_1$-regularized resistance

We study the basic problem of approximating the number of spanning trees of a graph. We propose an algorithm that approximates the number of spanning trees in $\tilde{O}(m+n^{7\mathrm{/}4}{\text{eps}}^{-3\mathrm{/}2})$ time on a graph with $n$ vertices and $m$ edges. Our algorithm improves upon the previously best known $\tilde{O}(m+n^{15\mathrm{/}8}{\text{eps}}^{-7\mathrm{/}4})$ time algorithm by Chu, Gao, Peng, Sachdeva, Sawlani, and Wang [FOCS 2018] and the $\tilde{O}(m^{1.5}{\text{eps}}^{-1})$ time algorithm by Liu, Peng and Yang [FOCS 2026] when $m\ge n^{7\mathrm{/}6}$. Notably, our algorithm is based on the novel concept of ${\mathrm{\ell }}_1$-regularized resistance. We propose simple and efficient algorithms for computing ${\mathrm{\ell }}_1$-regularized resistance and we show that they can be used to approximate the number of spanning trees by combining with the determinant sparsifier framework of Durfee, Peebles, Peng, and Rao [FOCS 2017].