Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Sampling in Space Restricted Settings
event speaker icon
Anup Bhattacharya (IIT Delhi)
event date icon
Wednesday, 01.07.2015, 12:30
event location icon
Taub 201
We consider the random sampling problem in the streaming setting. The algorithm returns, at any time t, an item chosen uniformly at random from all items seen till time t. Our model allows storage for only one item at a time in the stream. We design an algorithm that takes O(log n) random bits and O(log n) space to maintain a random sample at all times. Our algorithm in the streaming setting matches the lower bound on the amount of required randomness for uniform sampling in the offline setting.

We also extend the work on sampling in the query model by Bringmann and Larsen (STOC 2013) to the approximate setting and obtain almost matching upper and lower bounds for the problem.

Joint work with: Davis Issac, Ragesh Jaiswal and Amit Kumar