Spectral Sparsification via Bounded-Independence Sampling

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$,andanerrorparameter$\epsilon > 0$,ouralgorithmrunsinspace$\tilde{O}(k\log (N\cdot w_{$\mathrm{m}\mathrm{a}\mathrm{x}$}/w_{$\mathrm{m}\mathrm{i}\mathrm{n}$}))$where$w_{$\mathrm{m}\mathrm{a}\mathrm{x}$}$and$w_{$\mathrm{m}\mathrm{i}\mathrm{n}$}$ are the maximum and minimum edge weights in $G$, and produces a weighted graph $H$ with $\tilde{O}(n^{1+2\mathrm{/}k}\mathrm{/}{ϵ}^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.