Insertion time of random walk cuckoo hashing

Presented as part of the Workshop on Algorithms and Randomness on May 15, 2018 at 9:30 a.m. in the Klaus Advanced Computing Building, Room 1116.Alan Frieze is a University Professor in the Department of Mathematical Sciences at Carnegie Mellon University. His main research interest is Probabilistic Combinatorics and its applications in Theoretical Computer Science and Operations Research.Runtime: 32:36 minutesWe consider the expected insertion time of Cuckoo Hashing when clashes are resolved randomly. We prove O(1) expected time insertion in two cases: (i) d choices of location and location capacity one: joint with Tony Johansson. (ii) 2 choices of location and location capacity d: joint with Samantha Pett