A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
Lawrence Li, Sushant Sachdeva · Society for Industrial and Applied Mathematics eBooks · 2023
We demonstrate that for expander graphs, for all ε > 0, there exists a data structure of size Õ(nε-1) which can be used to return (1 + ε)-approximations to effective resistances in Õ(1) time per query. Short of storing all effective resistances, previous best approaches could achieve Õ(nε-2) size and Õ (ε-2) time per query by storing Johnson-Lindenstrauss vectors for each vertex, or Õ (nε-1) size and Õ (nε-1) time per query by storing a spectral sketch.