CS Events
SeminarAlgorithms for Massive Graphs via Linear Sketching |
|
||
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