CS 269S, Winter 2011: Theory Seminar
Bren Hall, Room 1427
11 Mar 2011:

The Power of Simple Tabulation Hashing

Michael Bannister, UC Irvine

The simplest possible form of tabulation hashing provides unexpectedly strong guarantees. The presentation will focus on the analysis of tabulation hashing for linear probing and cuckoo hashing.

(Based on a paper by Mihai Pătraşcu and Mikkel Thorup to be presented at STOC 2011.)