Loading Events

« All Events

  • This event has passed.

Fishbowl teleseminar: The Power of Choice : Simple Hash-Based Data Structures Everyone Should Know

October 17, 2012 @ 3:00 pm - 5:00 pm

Prof. Michael Mitzenmacher
Professor of Computer Science
Harvard University



Many computing tasks, particularly in networking, databases, or other areas with large quantities of information, now make use of hash-based data structures. Specific examples include Bloom filters, multiple-choice hashing schemes, and cuckoo hashing. We review the basics and history of these data structures, explaining why they have become a key algorithmic building block. We examine both the mathematics underlying their performance and real-world applications. The talk is intended to be an introduction; no previous knowledge of hashing is required.



Michael Mitzenmacher is a Professor of Computer Science (and currently Area Dean for Computer Science) in the School of Engineering and Applied Sciences at Harvard University. Michael has authored or co-authored over 150 conference and journal publications on a variety of topics, including algorithms for the Internet, efficient hash-based data structures, erasure and error-correcting codes, power laws, and compression. His work on low-density parity-check codes shared the 2002 IEEE Information Theory Society Best Paper Award and won the 2009 ACM SIGCOMM Test of Time
Award. His textbook on randomized algorithms and probabilistic techniques in computer science was published in 2005 by Cambridge University Press.

Michael Mitzenmacher graduated summa cum laude with a B.A. in mathematics and computer science from Harvard in 1991. After studying mathematics for a year in Cambridge, England, on the Churchill Scholarship, he obtained his Ph. D. in computer science at U.C. Berkeley in 1996. He then worked at Digital Systems Research Center until joining the Harvard faculty in 1999.


October 17, 2012
3:00 pm - 5:00 pm