Alexandr Andoni: Sketching Complexity of Graph Cuts

Tuesday, October 14, 2014 - 4:15pm to 5:15pm
Light Refreshments
G449 (Patil/Kiva)
Alexandr Andoni
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.