Date: November 10, 2025
Time: 3:45-5 p.m.
Location: Computing and Information Science Building, Room 450 or via Zoom
Speaker: Vinayak Kumar, UT Austin
Abstract: 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.
Bio: Vinayak Kumar is a Ph.D. student at UT Austin, advised by David Zuckerman. He received his B.S. in computer science and mathematics from Caltech in 2021. His research explores the role of randomness in computation—both how randomness can enhance computational power and how it can be leveraged to prove computational limitations. His research is supported by a Jane Street Fellowship and has been recognized with a Best Student Paper Award at STOC 2024.