Talk “Probabilistic Data Structures in Adversarial Environments”
Speaker: Prof. Marc Fischlin
2025/05/21 17:15-19:00
Location: TU Darmstadt, Hörsaal der Kernphysik (S2|14 24), Schlossgartenstr. 9, 64289 Darmstadt
Organizer: Department of Mathematics, Prof. Dr. Giesselmann
Prof. Marc Fischlin will give a talk on “Probabilistic Data Structures in Adversarial Environments” at the Mathematical Colloquium.
Abstract
Data structures provide a mechanism to organize data, usually providing methods to insert, delete, and search elements. Probabilistic data structures such as skip lists, hash tables, and Cuckoo hashing use randomized strategies to improve the efficiency, often yielding better average-case results for some operations. The performance analyses of these probabilistic data structures, however, usually hinge on non-adversarially chosen inputs.
In this talk we discuss that these performance guarantees cannot be upheld for maliciously chosen data and present remedies against such vulnerabilities.
