Events
Spring 2016

Counting Program Seminar Series

Mar 11, 2016 2:00 pm – 3:00 pm 

Add to Calendar

Speaker: 

Alan Frieze (Carnegie Mellon University)

Location: 

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