Spectral sparsification via bounded-independence sampling

Citation:

Doron, Dean, Jack Murtagh, Salil Vadhan, and David Zuckerman. Spectral sparsification via bounded-independence sampling. Electronic Colloquium on Computational Complexity (ECCC), TR20-026, 2020.
 ECCC 2020.pdf 1.15 MB

Abstract:

Version History:

v1, 26 Feb 2020: https://arxiv.org/abs/2002.11237

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.

Publisher's Version

Last updated on 06/22/2020