Alexandr Andoni: Sketching Complexity of Graph Cuts

Speaker: Alexandr Andoni

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

Public: Yes

Location: G449 (Patil/Kiva)

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,,

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Deborah Goodwin Email at Wednesday, October 08, 2014 at 9:45 AM.