Events
Spring 2016
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/cc_logo_final_v2_full.png?itok=H2qN2xxW)
Counting Program Seminar Series
Friday, March 11th, 2016, 2:00 pm–3:00 pm
Parent Program:
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