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 Ω( n 2 ) recovery time [Kapralov et al. ‘14], or ran in o ( n 2 ) 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 log O (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.

Authors

• Michael Kapralov
• Aida Mousavifar
• Cameron Musco
• Christopher Musco
• Navid Nouri
• Aaron Sidford
• Jakab Tardos

Keywords

No keywords are indexed for this paper.