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

We demonstrate that for expander graphs, for all ε > 0, there exists a data structure of size O(nε -1 ) which can be used to return (1 + ε)-approximations to effective resistances in O(1) time per query. Short of storing all effective resistances, previous best approaches could achieve O(nε -2 ) size and O(ε -2 ) time per query by storing Johnson-Lindenstrauss vectors for each vertex, or O(nε -1 ) size and O(nε -1 ) time per query by storing a spectral sketch.

Our construction is based on two key ideas: 1) ε -1 -sparse, ε-additive approximations to σu for all u, vectors similar to DL + 1u, can be used to recover (1 + ε)-approximations to the effective resistances, 2) In expander graphs, only O(ε -1 ) coordinates of σu are larger than ε. We give an efficient construction for such a data structure in O(m + nε -2 ) time via random walks. This results in an algorithm on expander graphs for computing (1 + ε)-approximate effective resistances for s vertex pairs that runs in O(m + nε -2 + s) time, improving over the previously best known running time of m 1+o(1) + (n + s)n o(1) ε -1.5 for s = ω(nε -0.5 ).

We employ the above algorithm to compute a (1 + δ)-approximation to the number of spanning trees in an expander graph, or equivalently, approximating the (pseudo)determinant of its Laplacian in O(m + n 1.5 δ -1 ) time. This improves on the previously best known result of m 1+o(1) + n 1.875+o(1) δ -1.75 time, and matches the best known size of determinant sparsifiers.