- Alexandr Andoni: Sketching ...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in October 2014

## 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, dlehto@csail.mit.edu

**Speaker URL:**
None

**Speaker Photo:**

None

**Reminders to:**
cis-seminars@csail.mit.edu, seminars@csail.mit.edu, theory-seminars@csail.mit.edu

**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:**

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