## Páll Melsted (23/10/15)

Math Colloquium

### Speaker: Páll Melsted

Title: Space Utilization of Cuckoo Hashtables

Location: V-157, VRII.

Time: Friday, October 23, at 15:00-16:00.

### Abstract:

We study the space requirements for Cuckoo Hashing. This can be reduced to

the following question in Random Graphs.

We are given two disjoint sets L,R with |L|=n=alpha*m and |R|=m. We construct a random graph G by allowing each x in L to choose d random neighbours in R. The problem is to find m(G), the size of the largest matching in G.

From the point of view of Cuckoo Hashing, a key question is to locate the threshold for when m(G)=n with high probability, since if m(G) < n it is impossible to store all items. We answer this question exactly for all values of d.