A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs

We demonstrate that for expander graphs, for all $ε> 0,$ there exists a data structure of size $\widetilde{O}(nε^{-1})$ which can be used to return $(1 + ε)$-approximations to effective resistances in $\widetilde{O}(1)$ time per query. Short of storing all effective resistances, previous best approaches could achieve $\widetilde{O}(nε^{-2})$ size and $\widetilde{O}(ε^{-2})$ time per query by storing Johnson-Lindenstrauss vectors for each vertex, or $\widetilde{O}(nε^{-1})$ size and $\widetilde{O}(nε^{-1})$ time per query by storing a spectral sketch. Our construction is based on two key ideas: 1) $ε^{-1}$-sparse, $ε$-additive approximations to $DL^+1_u$ for all $u,$ can be used to recover $(1 + ε)$-approximations to the effective resistances, 2) In expander graphs, only $\widetilde{O}(ε^{-1})$ coordinates of a vector similar to $DL^+1_u$ are larger than $ε.$ We give an efficient construction for such a data structure in $\widetilde{O}(m + nε^{-2})$ time via random walks. This results in an algorithm for computing $(1+ε)$-approximate effective resistances for $s$ vertex pairs in expanders that runs in $\widetilde{O}(m + nε^{-2} + s)$ time, improving over the previously best known running time of $m^{1 + o(1)} + (n + s)n^{o(1)}ε^{-1.5}$ for $s = ω(nε^{-0.5}).$ We employ the above algorithm to compute a $(1+δ)$-approximation to the number of spanning trees in an expander graph, or equivalently, approximating the (pseudo)determinant of its Laplacian in $\widetilde{O}(m + n^{1.5}δ^{-1})$ time. This improves on the previously best known result of $m^{1+o(1)} + n^{1.875+o(1)}δ^{-1.75}$ time, and matches the best known size of determinant sparsifiers.