Towards Optimal Effective Resistance Estimation

Rajat Vadiraj Dwaraknath, Ishani Karmarkar, Aaron Sidford

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 $\widetilde{O…