Talk „Probabilistic Data Structures in Adversarial Environments“
Speaker: Prof. Marc Fischlin
21.05.2025 17:15-19:00
Location: TU Darmstadt, Hörsaal der Kernphysik (S2|14 24), Schlossgartenstr. 9, 64289 Darmstadt
Veranstalter: Fachbereich Mathematik, Prof. Dr. Giesselmann
Prof. Marc Fischlin wird auf dem Mathematischen Kolloguium zum Thema „Probabilistic Data Structures in Adversarial Environments“ sprechen.
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.
