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: Bloom Filters in Adversarial Environments
event speaker icon
Eylon Yogev (Weizmann Institute of Science)
event date icon
Wednesday, 21.10.2015, 12:30
event location icon
Taub 201
Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and/or correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure. In this talk, I'll consider data structures in a more robust model, which we call the adversarial model. Roughly speaking, this model allows an adversary to choose inputs and queries adaptively according to previous responses. Specifically, I'll consider a data structure known as "Bloom filter" and prove a tight connection between Bloom filters in this model and cryptography.

Joint work with Moni Naor.