The Sketching Complexity of Graph Cuts

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.

We also show that if one is interested only in the property that a fixed cut is approximated up to 1+eps with high probability, then there is a data structure using only O~(n/eps) bits of space, and this is optimal up to polylogarithmic factors. This suffices for applications such as min-cut, and shows a separation between the "for-each" and "for-all" problems for cut approximation.

Joint work with Alex Andoni and Robi Krauthgamer
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.