Loading jsMath...
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: 342
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