Málstofa í stærðfræði

Fyrirlesari: Páll Melsted
Titill: Space Utilization of Cuckoo Hashtables

Staðsetning: V-157, VRII.
Tími: Föstudagur 23. október, klukkan 15:00-16:00.

Ágrip:

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.