[Colloquium] REMINDER: 8/10 TTIC Colloquium: Sanjeev Khanna, University of Pennsylvania

[Mary Marre]

When:     Monday, August 10th at 11:00 a.m.

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Speaker:  Sanjeev Khanna, University of Pennsylvania

Title: Approximate Matchings in Dynamic Graph Streams


Abstract:

We consider the problem of approximating a maximum matching in dynamic
graph streams where the input graph is revealed as a stream of edge updates
that may include both edge insertions and deletions. The goal is to design
a streaming algorithm that computes an approximate matching in sublinear
space. Essentially, the only known technique for designing algorithms in
the dynamic streaming model is linear sketching where the algorithm
maintains a linear projection of the input data. In this talk, we will
present a complete resolution of the space needed to approximate maximum
matching via linear sketching in the dynamic streaming model. Combined with
a recent characterization of dynamic streaming algorithms, this in fact
resolves the space complexity of approximating matchings by any streaming
algorithm.

This is based on joint work with Sepehr Assadi, Yang Li, and Grigory
Yaroslavtsev.


*Host:* Julia Chuzhoy


For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php




Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150809/81a4aba5/attachment.htm