CSD Faculty Candidate
— 12:00pm
Location:
In Person and Virtual - ET
-
Newell-Simon 4305 and Zoom
Speaker:
WILLIAM KAUZMAUL
,
Ph.D. Student, Electrical Engineering and Computer Science Department, Massachusetts Institute of Technology
https://sites.google.com/site/williamkuszmaul/
Randomized Data Structures: Modern Perspectives and Hidden Surprises
In this talk, we will discuss the remarkable power of randomization as a tool to design better data structures. We argue that, for many classical algorithmic problems, including those that have been studied for decades, there remain opportunities to unlock hidden surprises by using randomization in just the right way.
We begin by revisiting one of the oldest data structures in computer science: the linear-probing hash table. We show that, by just slightly modifying how randomness is used in the hash table, one can significantly improve the hash table's asymptotic performance at high load factors. In the process, we overturn a 60-year-old conventional wisdom on the amortized complexity of linear probing.
We also use randomization to break through seemingly fundamental barriers on two other problems. We give a new solution to the dynamic-sorting problem, representing the first algorithmic improvement to the problem in 40 years. And we introduce a technique for using randomization to compress pointer-based data structures so that pointers can be encoded using a sub-logarithmic number of bits---this final example comes with an unexpected application to improving the performance of hardware TLBs (translation lookaside buffers).
—
William Kuszmaul is a Ph.D. student at MIT EECS, where he specializes in the design and analysis of randomized algorithms and data structures. He has resolved long-standing open problems on space-efficient hashing, randomized load balancing, stochastic generalized sorting, etc., and his papers have won numerous Best Paper, Best Paper Finalist, and Best Student Paper awards. He is a recipient of both the Hertz Fellowship and the NSF GRFP Fellowship.
Faculty Host: Guy Blelloch
In Person and Zoom Participation. See announcement.