BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Heavy hitters via cluster-preserving clustering
DTSTART:20160720T111500
DTSTAMP:20260610T191431Z
UID:4feb5157ed452f53e602c637469228f7b853fb9a3f0fda80e604002d
CATEGORIES:Conferences - Seminars
DESCRIPTION:Jelani Nelson\, Harvard University\nAbstract:\nPreviously it w
 as known that all l2 eps-heavy hitters could be found in the turnstile mod
 el in optimal O((1/eps^2) lg n) words of space with O(lg n) update time an
 d very slow O(n lg n) query time with 1/poly(n) failure probability\, via 
 the CountSketch of Charikar\, Chen and Farach-Colton. The query time could
  be improved drastically using the "dyadic trick" to O((1/eps^2) poly(lg n
 ))\, but the space and update time worsened to log^2n to achieve such smal
 l failure probability. We show that the best of all worlds is possible: we
  give a new algorithm\, ExpanderSketch\, achieving O((1/eps^2) lg n) space
 \, O(lg n) update time\, and O((1/eps^2) poly(lg n)) query with 1/poly(n) 
 failure probability. This is accomplished via a new reduction from the hea
 vy hitters problem to a graph clustering problem of independent interest\,
  which we solve using a new clustering algorithm CutCloseGrab which is gua
 ranteed to find every single cluster regardless of the number of clusters 
 or the comparative sizes between the cluster and the entire graph.\nJoint 
 work with Kasper Green Larsen\, Huy L. Nguyen\, and Mikkel Thorup.\nBio:\n
 Jelani Nelson is an Assistant Professor of Computer Science at Harvard Uni
 versity. He is broadly interested in algorithms\, with some specific inter
 ests in streaming and sketching algorithms\, dimensionality reduction\, co
 mpressed sensing\, and randomized linear algebra.  
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR