Towards Optimal Effective Resistance Estimation

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.