The Sketching Complexity of Graph Cuts
Principles & Methodologies Group at IBM Almaden Research Center
Tuesday, November 11, 2014|
4:00pm - 5:30pm
Add to Google Calendar
About the Event
We show an Omega(n/eps^2) bit lower bound for any data structure which reports (1+eps)-approximate values to all cuts of an unweighted graph. In the special case where the sketch is itself a weighted graph (which may or may not be a subgraph) and the estimator is the sum of edge weights across the cut in the sketch, i.e., a cut sparsifier, we show the sketch must have Omega(n/eps^2) edges, which is optimal up to a constant factor. Despite the long sequence of work on graph sparsification, no such lower bound was known on the size of a cut sparsifier.
David Woodruff received his Ph.D. from MIT in 2007 and has been a research scientist at IBM Almaden since then. He has received several awards including best paper awards in STOC and PODS, and the Presburger award. He is the author of the monograph "Sketching as a Tool for Numerical Linear Algebra". His research interests are in the area of big data, including communication complexity, compressed sensing, data streams, machine learning, and numerical linear algebra.
Open to: Public