Linear Hashing Is Optimal | Awesome Similarity Search Papers

Linear Hashing Is Optimal

Michael Jaber, Vinayak M. Kumar, David Zuckerman · STOC '25: 57th Annual ACM Symposium on Theory of Computing · 2025

We prove that hashing (n) balls into (n) bins via a random matrix over (\mathbf{F}_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\cdotlog n/loglog n) with probability at most (O(1/r^2)).

Explore more on:
Uncategorized
Similar Work
Loading…