  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 $\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.
