DIMACS Theoretical Computer Science Seminar

Title: Algorithms for Massive Graphs via Linear Sketching

Speaker: Andrew McGregor, University of Massachusetts

Date: Wednesday, March 23, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ


In this talk, we will survey recent work on using random linear projections, a.k.a. sketches, to analyze massive graphs. Sketches are useful in a variety of computational models including the dynamic graph stream model were the input is defined by a stream of edge insertions and deletions that need to be processed in small space. A large number of problems have now been studied in this model including edge and vertex connectivity, spectral sparsification, triangle counting, densest subgraph, correlation clustering, vertex cover, and matching.

See: http://www.cs.rutgers.edu/~allender/theory-spring16.html