论文标题
一种估计有效阻力和计数跨越树木的新方法
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
论文作者
论文摘要
我们证明，对于所有$ε> 0，存在一个大小$ \ wideTilde {o}（nε^{ - 1}）$的数据结构，该数据结构可用于返回$（1 +ε）$ - 在$ \ wideTilde {o}（1）$ per Per Per ucer peer的$ \ wideTilde {o} $ \ \ wideTildeL {o \ wideTildeDem-time time的有效电阻上的近似值。缺乏存储所有有效的阻力，以前的最佳方法可以实现$ \ wideTilde {o}（nε^{ - 2}）$ size和$ \ \ \ \ widetilde {o}（ε^{ - 2}）$每询问的时间，通过存储Johnson-lindenstrauss vectors for gohnson-lindenstrauss vectors for yous ajohnson-lindenstrauss vectors for vertex，或$ \ wideteLdeLde $} $}（and）（或1） $ \ widetilde {o}（nε^{ - 1}）$ $ $通过存储频谱草图。 我们的构建基于两个关键想法：1）$ε^{ - 1} $ - 稀疏，$ε$ - addized近似于$ dl^ + 1_U $，用于所有$ u，$可用于恢复$（1 +ε）$ - 在有效的阻力上的近似值，仅在扩张图中，只有$ \ widetiLde of $ \ widetiLde of a $ \ \ \ \ \ \ fidetielde a $} $} - 到$ dl^ + 1_U $大于$ε。$我们在$ \ widetilde {o}（m +nε^{ - 2}）$ time $ \ widetilde {o}中提供了有效的结构。这导致了用于计算$（1 +ε）$的算法 - $ s $ s $顶点的近似有效电阻在扩展器中运行，该电阻以$ \ \ \ widetilde {o}（m +nε^{ - 2} + s）$ time，比以前最著名的运行时间改善了$ M^{1 + M^{1 + O（1 + O（1 + O（1） +（1 + O（N s）n^{o（1）}ε^{ - 1.5} $ for $ s =ω（nε^{ - 0.5}）。$ 我们采用上述算法来计算$（1 +δ）$ - 与扩展器图中的跨越树的数量近似，或等效地近似于其laplacian的（伪）决定因素，以$ \ widetilde {o}（m + n^{1.5}Δ^^Δ^Δ^{-1}}）$。这改善了$ m^{1+o（1）}+n^{1.875+o（1）}δ^{ - 1.75} $ time的$ M^{1+O（1）}+n^{1+o（1）} $ n^{ - 1.75} $ time的结果，并匹配确定性稀疏器的最著名大小。
We demonstrate that for expander graphs, for all $ε> 0,$ there exists a data structure of size $\widetilde{O}(nε^{-1})$ which can be used to return $(1 + ε)$-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ε^{-2})$ size and $\widetilde{O}(ε^{-2})$ time per query by storing Johnson-Lindenstrauss vectors for each vertex, or $\widetilde{O}(nε^{-1})$ size and $\widetilde{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 $DL^+1_u$ for all $u,$ can be used to recover $(1 + ε)$-approximations to the effective resistances, 2) In expander graphs, only $\widetilde{O}(ε^{-1})$ coordinates of a vector similar to $DL^+1_u$ are larger than $ε.$ We give an efficient construction for such a data structure in $\widetilde{O}(m + nε^{-2})$ time via random walks. This results in an algorithm for computing $(1+ε)$-approximate effective resistances for $s$ vertex pairs in expanders that runs in $\widetilde{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 $\widetilde{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.
