@conference {650524,
title = {Spectral sparsification via bounded-independence sampling},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
volume = {168},
year = {2020},
pages = {39:1-39:21},
publisher = {Leibniz International Proceedings in Informatics (LIPIcs), Schloss-Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik},
organization = {Leibniz International Proceedings in Informatics (LIPIcs), Schloss-Dagstuhl-Leibniz-Zentrum f{\"u}r Informatik},
abstract = {
Version History:
v1, 26 Feb 2020:\ https://arxiv.org/abs/2002.11237
Full version published as ECCC TR20-026.
View a YouTube recording of John Peebles{\textquoteright} 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{\textquoteright}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.
},
url = {https://drops.dagstuhl.de/opus/volltexte/2020/12446/},
author = {Dean Doron and Jack Murtagh and Salil Vadhan and David Zuckerman}
}