CS Colloquium
Thursday, October 22, 2009
4:00 p.m., AKW 200

Sign up to meet with speaker.

Host: Joan Feigenbaum

Speaker: Michael Mitzenmacher, Harvard University
Title: Some Open Questions Related to Cuckoo Hashing

Abstract: In this talk, we will describe cuckoo hashing, a recently developed hashing scheme that offers the benefits of very high memory utilization and worst-case constant lookup times. We then discuss recent work in the area, including theoretical bounds on performance, practical methods for improving performance, and implementations on a GPU. Along the way, we will suggest several remaining open questions.

The talk will require no prior background on cuckoo hashing, and is aimed for a wide audience, including both theory and systems.

Bio: Michael Mitzenmacher is a Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 100 conference and journal publications on a variety of topics, including Internet algorithms, hashing, load-balancing, erasure codes, error-correcting codes, compression, bin-packing, and power laws. His work on low-density parity-check codes received the 2002 IEEE Information Theory Society Best Paper Award and the 2009 SIGCOMM Test of Time Award. His textbook on probabilistic techniques in computer science, co-written with Eli Upfal, was published in 2005 by Cambridge University Press.