BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Streaming Symmetric Norms via Measure Concentration
DTSTART:20170614T145000
DTEND:20170614T153500
DTSTAMP:20260930T210024Z
UID:ce87b88df9c8791d44800933300d0f33600a2e832ef69149e37cb9f4
CATEGORIES:Conferences - Seminars
DESCRIPTION:Robert Krauthgamer\, The Weizmann Institute of Science\nA long
  line of research studies the space complexity of estimating a norm l(x) i
 n the data-stream model\, i.e.\, when x is the frequency vector of an inpu
 t stream which consists of insertions and deletions of n item types.\nRest
 ricting attention to norms l (on R^n) that are symmetric\, meaning that l 
 is invariant under sign-flips and coordinate-permutations\, I will show th
 at the streaming space complexity is essentially determined by the measure
 -concentration characteristics of l. The same quantity is known to govern 
 many phenomena in high-dimensional spaces\, such as large-deviation bounds
  and the critical dimension in Dvoretzky's Theorem.\nThe family of symmetr
 ic norms contains several well-studied norms\, such as all l_p norms\, and
  indeed we provide a new explanation for the disparity in space complexity
  between p<=2 and p>2. We also obtain bounds for other norms that are usef
 ul in applications.\nJoint work with Jaroslaw Blasiok\, Vladimir Braverman
 \, Stephen R. Chestnut\, and Lin F. Yang.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR