Please note: This seminar will take place in DC 1304 and online.
Vinayak Kumar, PhD student
Computer Science Theory Group, UT Austin
When n balls are independently and uniformly tossed into n bins, the expected max-load — the number of balls in the heaviest bin — is O(logn/loglogn). This classical result plays a central role in the analysis of hashing with chaining and load balancing. However, implementing a truly random hash function is often impractical due to its high computational and storage costs.
In this talk, I will present a recent result showing that hashing n balls into n bins via a random matrix over F2 achieves the same expected max-load of O(logn/loglogn). This simple and efficient hash family matches the performance of a fully random function and resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos.
Based on joint work with Michael Jaber and David Zuckerman.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.