Linear Hashing with ${\ell }_{\infty }$ guarantees and two-sided Kakeya bounds

Manik Dhar, Zeev Dvir

We show that a randomly chosen linear map over a finite field gives a good hash function in the ${\ell }_{\infty }$ sense. More concretely, consider a set $S\subset {\mathbb{F}}_q^n$ and…