Seminar Details
Balls and Bins and Icebergs
- Start Date: November 18, 2020
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Organizers: Sepehr Assadi || Swastik Kopparty
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Martin Farach-Colton - Rutgers University
- Event Location: Online Event
- Event Additional Info: <p>Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://sites.google.com/view/dimacs-theory-seminar/home">https://sites.google.com/view/dimacs-theory-seminar/home</a></p> <p> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Abstract:
Balls and bins games are a standard technique for analyzing hashing algorithms. Backyards are a technique for making hash tables faster. We give a balls and bins analysis of backyarding, yielding Iceberg Hashing, a hashing scheme that achieves optimal performance along several dimensions — times, space, failure probability, resizing, stability — and which solves several open problems. In the mean time, we also solve an open problem balls and bins: we give a tight bound on the fullest bin in dynamic balls and bins games.