Citation:
 | ECCC 2020.pdf | 1.15 MB |
| ICALP 2020.pdf | 580 KB |
| ACM 2023.pdf | 737 KB |
Abstract:
- v1, 26 Feb 2020: https://arxiv.org/abs/2002.11237
- Full preliminary versions in Pro. ICALP '20 (47th International Colloquium on Automata, Languages, and Programming 2020, Vol. 168, pgs. 39:1-39:21) and published as ECCC TR20-026.
- View a YouTube recording of John Peebles' talk on this paper, recorded at FOCS 2020.
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 \(\varepsilon > 0\), our algorithm runs in space \(\tilde{O}(k \log(N ^. w_{max}/w_{min}))\) where \(w_{max}\) and \(w_{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.