Organizer(s):

Sepehr Assadi, Rutgers University

Swastik Kopparty, Rutgers University

Martin Farach-Colton, Rutgers University

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.

Location: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. 

See: https://sites.google.com/view/dimacs-theory-seminar/home