The ACO Seminar (2014–2015)

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 ℓ₂/ℓ₂ 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.