Nov. 13, 3:30pm, Wean 8220

Mikhail Kapralov, IBM Watson

Spectral Sparsification in Dynamic Streams

Mikhail Kapralov, IBM Watson

Spectral Sparsification in Dynamic Streams

Abstract:

Graph sparsification is a standard algorithmic tool for reducing the number of edges in a graph while approximately preserving its structural properties.
Sparsification is especially important when the input graph is so large that its edge set cannot be stored in memory, a setting modeled by the
well-studied streaming model of computation.

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}*/ℓ

Joint work with Yin Tat Lee, Cameron Musco, Christopher Musco and Aaron Sidford.