All reports by Author Manik Dhar:

__
TR22-047
| 4th April 2022
__

Manik Dhar, Zeev Dvir#### Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

Revisions: 1

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 a randomly chosen linear map $L : \mathbb{F}_q^n \to \mathbb{F}_q^t$ with $q^t$ taken to be sufficiently smaller than $|S|$. Let ... more >>>