Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MANIK DHAR:
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

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 >>>




ISSN 1433-8092 | Imprint