Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

arXiv:2204.01665v3 Announce Type: cross
Abstract: 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 $U_S$ denote a random variable distributed uniformly on $S$. Our main theorem shows that, with high probability over the choice of $L$, the random …

arxiv cs.cc cs.cr function good hash hash function hashing linear map math.co taken