![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Description
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
All scheduled dates:
Upcoming
No Upcoming activities yet