Spectral Sparsification via Bounded-Independence Sampling

Dean Doron, Jack Murtagh, Salil Vadhan +1

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…