BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//MIT Center for Statistics - ECPv4.6//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:MIT Center for Statistics
X-ORIGINAL-URL:https://stat.mit.edu
X-WR-CALDESC:Events for MIT Center for Statistics
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20170929T110000
DTEND;TZID=America/New_York:20170929T120000
DTSTAMP:20180119T074150
CREATED:20170801T015204Z
LAST-MODIFIED:20170921T181855Z
UID:1679-1506682800-1506686400@stat.mit.edu
SUMMARY:Optimal lower bounds for universal relation\, and for samplers and finding duplicates in streams
DESCRIPTION:Abstract: Consider the following problem: we monitor a sequence of edgeinsertions and deletions in a graph on n vertices\, so there are N = (n choose 2) possible edges (e.g. monitoring a stream of friend accepts/removals on Facebook). At any point someone may say “query()”\, at which point must output a random edge that exists in the graph at that time from a distribution that is statistically close to uniform. More specifically\, with probability p our edge should come from a distribution close to uniform\, and with probability 1-p our sampler can do anything (i.e. it can say “Fail”\, or output a non-existent edge). The primary goal is to design an algorithm that uses very little memory. Whereas the trivial solution maintains N bits\, keeping track of which edges currently exist\, we show that the optimal space complexity for this problem is Theta(min{N\, log(1/p) * log^2(2 + N / log(1/p))}) bits. The upper bound follows by a very minor modificationof previous work\, whereas the lower bound is our main novel contribution.This is joint work with Michael Kapralov (EPFL)\, Jakub Pachocki (OpenAI)\, Zhengyu Wang (Harvard)\, David P. Woodruff (IBM Almaden)\, and Mobin Yahyazadeh (Sharif). \nBiography: Jelani Nelson is Associate Professor of Computer Science at Harvard. His main research interest is in algorithm design and analysis\, with recent focus on streaming algorithms\, dimensionality reduction\, compressed sensing\, and randomized linear algebra algorithms. He completed his Ph.D. in computer science at MIT in 2011\, receiving the George M. Sprowls Award for best computer science doctoral dissertations at MIT. He is the recipient of an NSF CAREER Award\, ONR Young Investigator Award\, ONR Director of Research Early Career Award\, Alfred P. Sloan Research Fellowship\, and Presidential Early Career Award for Scientists and Engineers (PECASE). \n
URL:https://stat.mit.edu/calendar/optimal-lower-bounds-for-universal-relation-and-for-samplers-and-finding-duplicates-in-streams/
LOCATION:50 Ames Street\, Cambridge\, MA\, 02139
GEO:42.3620185;-71.0878444
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=50 Ames Street Cambridge MA 02139;X-APPLE-RADIUS=500;X-TITLE=50 Ames Street:geo:-71.0878444,42.3620185
CATEGORIES:Stochastics and Statistics Seminar
END:VEVENT
END:VCALENDAR