Towards Optimal Effective Resistance Estimation

Computing the effective resistance of nodes in a network (or, undirected graph) is a fundamental task with many applications, for instance, in graph machine learning, graph data analysis, and the design of efficient graph algorithms. In this paper we introduce new efficient algorithms for estimating effective resistances in well-connected graphs. We also prove improved time lower bounds for effective resistance estimation. In addition, we provide natural extensions of our work to related problems on symmetric diagonally dominant (SDD) and positive semi-definite (PSD) matrices. (arxiv)