ECCC-Report TR20-026https://eccc.weizmann.ac.il/report/2020/026Comments and Revisions published for TR20-026en-usMon, 20 Apr 2020 08:17:10 +0300
Revision 1
| Spectral Sparsification via Bounded-Independence Sampling |
Dean Doron,
Jack Murtagh,
Salil Vadhan,
David Zuckerman
https://eccc.weizmann.ac.il/report/2020/026#revision1We 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 $\epsilon > 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}/\epsilon^2)$ edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $\epsilon$.
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.Mon, 20 Apr 2020 08:17:10 +0300https://eccc.weizmann.ac.il/report/2020/026#revision1
Paper TR20-026
| Spectral Sparsification via Bounded-Independence Sampling |
Dean Doron,
Jack Murtagh,
Salil Vadhan,
David Zuckerman
https://eccc.weizmann.ac.il/report/2020/026We 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 $\varepsilon > 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}/\varepsilon^2)$ expected edges that spectrally approximates $G$, in the sense of Spielmen and Teng [ST04], up to an error of $\varepsilon$.
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. Wed, 26 Feb 2020 06:13:25 +0200https://eccc.weizmann.ac.il/report/2020/026