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 r Opmǫ ´1q-time algorithm that produces with high probability, an r Opnǫ ´1q-bit sketch from which the effective resistance between any pair of nodes can be estimated, to p1 ˘ǫq-multiplicative accuracy, in r Op1q-time. Consequently, we obtain an r Opmǫ ´1q-time algorithm for estimating the effective resistance of all edges in such graphs, improving (for sparse graphs) on the previous fastest runtimes of r Opmǫ ´32 q [1] and r Opn 2 ǫ ´1q [2] for general graphs and r Opm `nǫ ´2q for expanders [3] . 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 r Ωpn 2 ǫ ´12 q-time, improving upon the previous best such lower bound of r Ωpn 2 ǫ ´113 q [4]. 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. Definition 2 (Effective Resistance Sketch). We call a randomized algorithm an pT s , T q , sq-effective resistance sketch algorithm if given an input n-node, m-edge undirected, weighted graph G " pV, E, wq and ǫ P p0, 1q in time OpT s pG, ǫqq it creates a binary string of length OpspG, ǫqq from which when queried with any a, b P V , it outputs ra,b « ǫ r G pa, bq whp. in time OpT q pG, ǫqq. Effective resistance sketching algorithms immediately imply algorithms for the effective resistance estimation problem. We obtain our result by obtaining an p r Opnǫ ´1q, r Opmǫ ´1qq-effective resistance sketch algorithm for expanders (see Section 1.1 for a comparison to prior work).