Linear Hashing with ℓ_∞ guarantees and two-sided kakeya bounds

We show that a randomly chosen linear map over a finite field gives a good hash function in the ℓ∞ sense. More concretely, consider a set S ⊂ Fⁿ _q and a randomly chosen linear map L: Fⁿ _q → F^t _q with qt taKen to be sufficiently smaller than |S|. Let US denote a random variable distributed uniformly on S. Our main theorem shows that, with high probability over the choice of L, the random variable L(U_S) is close to uniform in the ℓ_∞ norm. In other words, every element in the range F^t _q has about the same number of elements in S mapped to it. This complements the widely-used Leftover Hash Lemma (LHL) which proves the analog statement under the statistical, or ℓ1, distance (for a richer class of functions) as well as prior work on the expected largest’bucKet size’ in linear hash functions [2]. By Known bounds from the load balancing literature [23], our results are tight and show that linear functions hash as well as truly random function up to a constant factor in the entropy loss. Our proof leverages a connection between linear hashing and the finite field KaKeya problem and extends some of the tools developed in this area, in particular the polynomial method.