CS Events

Seminar

Algorithms for Massive Graphs via Linear Sketching

 

Download as iCal file

Wednesday, March 23, 2016, 11:00am

 

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.

Speaker: Andrew McGregor

Bio

NULL

Location : Core A (Room 301)

Committee

Eric Allender, Pranjal Awasthi, Michael Saks and Mario Szegedy

Event Type: Seminar

Organization

University of Massachusetts