  We demonstrate that for expander graphs, for all $\epsilon > 0,$ there exists
a data structure of size $\widetilde{O}(n\epsilon^{-1})$ which can be used to
return $(1 + \epsilon)$-approximations to effective resistances in
$\widetilde{O}(1)$ time per query. Short of storing all effective resistances,
previous best approaches could achieve $\widetilde{O}(n\epsilon^{-2})$ size and
$\widetilde{O}(\epsilon^{-2})$ time per query by storing Johnson-Lindenstrauss
vectors for each vertex, or $\widetilde{O}(n\epsilon^{-1})$ size and
$\widetilde{O}(n\epsilon^{-1})$ time per query by storing a spectral sketch.
  Our construction is based on two key ideas: 1) $\epsilon^{-1}$-sparse,
$\epsilon$-additive approximations to $DL^+1_u$ for all $u,$ can be used to
recover $(1 + \epsilon)$-approximations to the effective resistances, 2) In
expander graphs, only $\widetilde{O}(\epsilon^{-1})$ coordinates of a vector
similar to $DL^+1_u$ are larger than $\epsilon.$ We give an efficient
construction for such a data structure in $\widetilde{O}(m + n\epsilon^{-2})$
time via random walks. This results in an algorithm for computing
$(1+\epsilon)$-approximate effective resistances for $s$ vertex pairs in
expanders that runs in $\widetilde{O}(m + n\epsilon^{-2} + s)$ time, improving
over the previously best known running time of $m^{1 + o(1)} + (n +
s)n^{o(1)}\epsilon^{-1.5}$ for $s = \omega(n\epsilon^{-0.5}).$
  We employ the above algorithm to compute a $(1+\delta)$-approximation to the
number of spanning trees in an expander graph, or equivalently, approximating
the (pseudo)determinant of its Laplacian in $\widetilde{O}(m +
n^{1.5}\delta^{-1})$ time. This improves on the previously best known result of
$m^{1+o(1)} + n^{1.875+o(1)}\delta^{-1.75}$ time, and matches the best known
size of determinant sparsifiers.
