Probabilistic Data Structures in Adversarial Environments

Probabilistic Data Structures (PDS) are heavily used nowadays as a means of dealing with big data, at the cost of only giving approximately correct answers to queries. Typical examples include HyperLogLog for approximate set cardinality estimation and Bloom filters for handling approximate set membership queries. In this talk I’ll focus on two basic questions:

1. What can go wrong when PDS are faced with adversarially-chosen input?
2. How can we protect PDS against manipulation in these adversarial environments?

Joint work with Mia Filic, Mathilde Raynal, Fernando Virdia, and Anupama Unnikrishnan.