BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:The Sketching Complexity of Graph Cuts
DTSTART:20150120T160000
DTEND:20150120T170000
DTSTAMP:20260505T122152Z
UID:12affc02c4702e3f71924fbf0ac43ecea6772e3227b7583957e25a10
CATEGORIES:Conferences - Seminars
DESCRIPTION:Robert Krauthgamer\, Professor\, Weizmann Institute of Science
 \nAbstract: \nWe study the problem of sketching an input graph $G$ on $n$
  vertices\, so that given (only) the sketch\, one can estimate the weight 
 (capacity) of any cut in the graph within a small approximation factor $1+
 \\epsilon$. The classic cut-sparsifier construction of Benczur and Karger 
 (STOC 1996) implies a sketch of size $\\tilde O(n/\\epsilon^2)$ [this nota
 tion hides logarithmic factors].\nWe show that the dependence on $\\epsilo
 n$ can be brought down to linear\, at the price of achieving a slightly re
 laxed guarantee. Specifically\, we design a randomized scheme that produce
 s from $G$ a sketch of size $\\tilde O(n/\\epsilon)$ bits\, from which the
  weight of any cut $(S\,\\bar S)$ can be reported\, with high probability\
 , within factor $1+\\epsilon$. We also demonstrate some applications where
  this "for each" guarantee is indeed useful.\nWe further prove that that o
 ur relaxation is necessary. Specifically\, a sketch that can $(1+\\epsilon
 )$-approximate the weight of all cuts in the graph simultaneously (a so-ca
 lled "for all" guarantee instead of "for each")\, must be of size $\\Omega
 (n/\\epsilon^2)$ bits.\nJoint work with Alexandr Andoni and David Woodruff
 .
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR