A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs

Lawrence Li, Sushant Sachdeva

We demonstrate that for expander graphs, for all $\epsilon >0,$ there exists a data structure of size $\tilde{O}(n{\epsilon }^{-1})$ which can be used to return $(1+\epsilon )$-approximations to effe…