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

arXiv: https://arxiv.org/abs/2211.01468 · HTML: https://mlsanity.com/paper/2211.01468/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2022.

## Built on by (most cited first, 2 of 2)

- [Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach](https://mlsanity.com/paper/2509.05129/) (2025)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

We demonstrate that for expander graphs, for all ε > 0, there exists a data structure of size widetildeO(nε-1) which can be used to return (1 + ε)-approximations to effective resistances in widetildeO(1) time per query. Short of storing all effective resistances, previous best approaches could achieve widetildeO(nε-2) size and widetildeO(ε-2) time per query by storing Johnson-Lindenstrauss vectors for each vertex, or widetildeO(nε-1) size and widetildeO(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^+1u for all u, can be used to recover (1 + ε)-approximations to the effective resistances, 2) In expander graphs, only widetildeO(ε-1) coordinates of a vector similar to DL^+1u are larger than ε. We give an efficient construction for such a data structure in widetildeO(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 widetildeO(m + nε-2 + s) time, improving over the previously best known running time of m1 + o(1) + (n + s)no(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 widetildeO(m + n1.5δ-1) time. This improves on the previously best known result of m1+o(1) + n1.875+o(1)δ-1.75 time, and matches the best known size of determinant sparsifiers.