Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-064 | 20th May 2025 10:21

Linear Hashing Is Optimal

RSS-Feed




TR25-064
Authors: Michael Jaber, Vinayak Kumar, David Zuckerman
Publication: 20th May 2025 11:59
Downloads: 395
Keywords: 


Abstract:

We prove that hashing $n$ balls into $n$ bins via a random matrix over $GF(2)$ yields expected maximum load $O(\log n / \log \log n)$. This matches the expected maximum load of a fully random function and resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC '97, JACM '99). More generally, we show that the maximum load exceeds $r\cdot \log n/\log\log n$ with probability at most $O(1/r^2)$.



ISSN 1433-8092 | Imprint