Alexandr Andoni: Sketching Complexity of Graph Cuts
Date: Tuesday, October 14, 2014
Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Location: G449 (Patil/Kiva)
Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan
Contact: Deborah Lehto, 617.324.7303, email@example.com
Speaker URL: None
firstname.lastname@example.org, email@example.com, firstname.lastname@example.org
TALK: Alexandr Andoni: Sketching Complexity of Graph Cuts
ABSTRACT: We study the problem of sketching an input graph so that, given the sketch, one can estimate the value (capacity) of any cut in the graph up to a small approximation, 1+epsilon. The classic construction of [Benczur, Karger 1996] implies a sketch of size essentially proportional
to the number of vertices and the *square* of 1/epsilon.
We show that the dependence on epsilon can be brought down to only linear in 1/epsilon, if one tolerates a slightly weaker guarantee. Namely, we give a randomized scheme which, given accuracy
epsilon and an n-vertex graph G=(V,E), produces a sketch of size O~(n/epsilon), from which one can report the capacity of any fixed cut
(S,V\S) within approximation factor (1+epsilon) with high probability. This "for each" guarantee remains useful in some applications nonetheless.
To complement the above, we also show that the weaker guarantee is inescapable to achieve the improved dependence on epsilon. In particular, if a sketch succeeds in estimating the capacity of *all* cuts in the graph simultaneously, it must have size at least Omega(n/epsilon^2) bits.
Joint work with Robert Krauthgamer and David Woodruff.
Created by Deborah Goodwin at Wednesday, October 08, 2014 at 9:45 AM.