AMS Seminar w/ Jelani Nelson ( University of California, Berkeley) on Zoom

March 18, 2021 @ 1:30 pm – 2:30 pm

Title: Memory lower bounds for sampling

Abstract: Suppose we would like to maintain a (multi)subset S of {1,…,n} dynamically subject to items being inserted into and deleted from S. Then when a user says “sample()”, we should return a (uniformly) random element of S, or an easier task, return just some (any) element in S. How much memory is required to accomplish this task? We answer
this question by giving an asymptotically optimal lower bound on the memory required.

Joint work with Michael Kapralov, Jakub Pachocki, Zhengyu Wang, David
P. Woodruff, and Mobin Yahyazadeh.


Here is the recording from the seminar:

Passcode: T&^!!4=C

Back to top