# Towards Optimal Effective Resistance Estimation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2023.

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

- [Efficient Reinforcement Learning for Global Decision Making in the Presence of Local Agents at Scale](https://mlsanity.com/paper/2403.00222/) (2024)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)
- [Generalized Inverses of Matrix Products: From Fundamental Subspaces to Randomized Decompositions](https://mlsanity.com/paper/2602.00386/) (2026)

## Abstract (arXiv)

We provide new algorithms and conditional hardness for the problem of estimating effective resistances in n-node m-edge undirected, expander graphs. We provide an widetildeO(mε-1)-time algorithm that produces with high probability, an widetildeO(nε-1)-bit sketch from which the effective resistance between any pair of nodes can be estimated, to (1 ± ε)-multiplicative accuracy, in widetildeO(1)-time. Consequently, we obtain an widetildeO(mε-1)-time algorithm for estimating the effective resistance of all edges in such graphs, improving (for sparse graphs) on the previous fastest runtimes of widetildeO(mε-3/2) [Chu et. al. 2018] and widetildeO(n2ε-1) [Jambulapati, Sidford, 2018] for general graphs and widetildeO(m + nε-2) for expanders [Li, Sachdeva 2022]. We complement this result by showing a conditional lower bound that a broad set of algorithms for computing such estimates of the effective resistances between all pairs of nodes require widetildeOmega(n2 ε-1/2)-time, improving upon the previous best such lower bound of widetildeOmega(n2 ε-1/13) [Musco et. al. 2017]. Further, we leverage the tools underlying these results to obtain improved algorithms and conditional hardness for more general problems of sketching the pseudoinverse of positive semidefinite matrices and estimating functions of their eigenvalues.