Fast and Space Efficient Spectral Sparsification in Dynamic Streams

In this paper, we resolve the complexity problem of spectral graph sparcification in dynamic streams up to polylogarithmic factors. Using a linear sketch we design a streaming algorithm that uses Õ(n) space, and with high probability, recovers a spectral sparsifier from the sketch in Õ(n) time.1 Prior results either achieved near optimal Õ(n) space, but Ω(n2) recovery time [Kapralov et al. ‘14], or ran in o(n2) time, but used polynomially suboptimal space [Ahn et al ‘13]. Our main technical contribution is a novel method for recovering graph edges with high effective resistance from a linear sketch. We show how to do so in nearly linear time by ‘bucketing’ vertices of the input graph into clusters using a coarse approximation to the graph's effective resistance metric. A second main contribution is a new pseudorandom generator (PRG) for linear sketching algorithms. Constructed from a locally computable randomness extractor, our PRG stretches a seed of Õ(n) random bits polynomially in length with just logO(1) n run-time cost per evaluation. This improves on Nisan's commonly used PRG, which in our setting would require Õ(n) time per evaluation. Our faster PRG is essential to simultaneously achieving near optimal space and time complexity.