BARC talk by Stefan Walzer

Monday, 16 May 2022, Stefan Walzer, a Postdoc at the University of Cologne, Germany, will give a talk on "Insertion Time of Random Walk Cuckoo Hashing below the Peeling".

Title:
Insertion Time of Random Walk Cuckoo Hashing below the Peeling

Abstract:
Most hash tables have an expected insertion time of O(1). While insertions into cuckoo hash tables indeed seem to take O(1) expected time in practice, only polylogarithmic guarantees are proven in all but the simplest of practically relevant cases.
In this paper, we show that random walk insertions into cuckoo hash tables take O(1) expected amortised time when any number k ≥ 3 of hash functions is used and the load factor is below the corresponding peeling threshold. Because the peeling threshold is less than the threshold up to which a placement of all keys exists (e.g. roughly 0.81 instead of

0.91 for k = 3), this is not quite the result one would hope for. It is still the first meaningful guarantee for constant time insertion for cuckoo hashing that works for k ∈ {3,…,9}.

Bio:
Stefan has studied math and computer science in Karlsruhe, Germany, before starting his PhD studies in Ilmenau, Germany, under the supervision of Martin Dietzfelbinger. His dissertation concerns random matrices and random hypergraphs that occur in the analysis of cuckoo hash tables and related randomised data structures.

Since December of 2020 he is a postdoc in the group of Christian Sohler in Cologne. He continues to work on cuckoo hashing and approximate membership data structures with funding from the German Research Foundation, but is also trying to get a foot in the door in other areas, such as sublinear time algorithms.