论文标题
光谱通过界定独立采样
Spectral Sparsification via Bounded-Independence Sampling
论文作者
论文摘要
我们给出了一种确定性的，几乎对数空间算法，用于对无向图的轻度光谱稀疏。给定$ n $顶点上的加权，无方向的图$ g $，由长度$ n $的二进制字符串，整数$ k \ leq \ log n $和错误参数$ε> 0 $，我们的算法在太空中运行$ \ tilde {o} w _ {\ mathrm {max}}/w _ {\ mathrm {min}}））$其中$ w _ {\ mathrm {max}} $和$ w _ {\ mathrm {minrm {min}} $是$ g $的最大和最小优势，以及$ g $的最大优势，$ $ $ $ $ $ $ $ $ h。 $ \ tilde {o}（n^{1+2/k}/ε^2）$边缘在Spielmen和Teng [ST04]的意义上，频谱近似于$ g $，最大为$ε$。 我们的算法基于Spielman和Srivastava的有效基于抗性的边缘采样算法的新界独立分析[SS08]，并使用了最新作品的laplacian Solvers的结果[MRSV17]。特别是，我们在边缘采样算法中使用的（有限）独立性的数量（通过上方和下限）表示了固有的权衡（通过上限和下限），该算法用上方的$ k $表示，以及可以实现的稀疏性。
We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$, and an error parameter $ε> 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot w_{\mathrm{max}}/w_{\mathrm{min}}))$ where $w_{\mathrm{max}}$ and $w_{\mathrm{min}}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $\tilde{O}(n^{1+2/k}/ε^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $ε$. Our algorithm is based on a new bounded-independence analysis of Spielman and Srivastava's effective resistance based edge sampling algorithm [SS08] and uses results from recent work on space-bounded Laplacian solvers [MRSV17]. In particular, we demonstrate an inherent tradeoff (via upper and lower bounds) between the amount of (bounded) independence used in the edge sampling algorithm, denoted by $k$ above, and the resulting sparsity that can be achieved.
