In the streaming model edges of the graph are presented to the algorithm as a sequence of edge insertions (insertion-only streams) or insertions and deletions (dynamic streams). Graph problems in the insertion only model have been studied extensively. On the other hand, small space solutions to even basic graph problems in the dynamic model have only been obtained very recently: in SODA'12 Ahn, Guha and McGregor gave a nearly optimal space algorithm for dynamic connectivity via linear measurements of the graph, starting the field of graph sketching.
In this talk I will present the first algorithm for constructing spectral sparsifiers of graphs in the dynamic model that takes only a single pass over the stream of edge updates and uses essentially optimal space. Our algorithm maintains a randomized linear sketch of the graph incidence matrix into dimension nearly linear in the number of vertices. Using this sketch, at any point, the algorithm can output a spectral sparsifier for the graph with high probability. The core of our approach is a novel application of ℓ2/ℓ2 sparse recovery that allows us to sample edges of the sketched graph with probabilities proportional to their effective resistance.
Joint work with Yin Tat Lee, Cameron Musco, Christopher Musco and Aaron Sidford.
Back to the ACO home page