When: Mar 18 2021 @ 1: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