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

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:
https://wse.zoom.us/rec/share/XXuuP3BmXqWAExrgjkyYorfi0dYfSS9q1ldhiI_5gGGZAFHnBqyyDqLOO0IOrWwt.PHPHN5296_mER36h
Passcode: T&^!!4=C