Graph Sketching

SHARE:

Event Speaker: 

Andrew McGregor, UMass Amherst

Event Location: 

32-124

Card Description: 

Applying random linear projections, a.k.a. "sketching", has become a standard technique when analyzing high-dimensional data sets. The resulting algorithms are embarrassingly parallelizable and suitable for stream processing.

Event Date/Time: 

Tuesday, September 25, 2012 - 4:15pm

Research Area: 

Graph Sketching

Speaker: Andrew McGregor, UMass Amherst
Date: Tuesday, September 25 2012
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: 32-124
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu

Relevant URL: 

Applying random linear projections, a.k.a. "sketching", has become a standard technique when analyzing high-dimensional data sets. The resulting algorithms are embarrassingly parallelizable and suitable for stream processing. However, existing results have largely focused on vector-based problems (e.g., estimating norms and reconstructing sparse signals) and linear-algebraic problems (e.g., regression and low-rank approximation). In this work, we ask whether the richer combinatorial structure of graphs can also be analyzed via small sketches. We present a range of algorithmic results and applications including the first single-pass algorithm for constructing graph sparsifiers of fully-dynamic graph streams (i.e., where edges can be added and deleted in the underlying graph). 

Based on joint work with Kook Jin Ahn and Sudipto Guha (SODA 12, PODS 12).

See other events that are part of Theory Colloquium 2012/2013

See other events happening in September 2012