Alan Frieze (Carnegie Mellon University)
Calvin Lab Room 116
On the Insertion Time of Random Walk Cuckoo Hashing
We show that the insertion time of a single element is O(1) in expectation. Mathematically, this amounts to showing that random walks tend to find short augmenting paths in a class of random bipartite graphs.
Joint with Tony Johansson