ECCC-Report TR22-047https://eccc.weizmann.ac.il/report/2022/047Comments and Revisions published for TR22-047en-usThu, 15 Sep 2022 18:25:12 +0300
Revision 1
| Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds |
Manik Dhar,
Zeev Dvir
https://eccc.weizmann.ac.il/report/2022/047#revision1We 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 variable $L(U_S)$ is close to uniform in the $\ell_\infty$ norm. In other words, {\em every} element in the range $\mathbb{F}_q^t$ 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 $\ell_1$, distance (for a richer class of functions) as well as prior work on the expected largest 'bucket size' in linear hash functions [ADMPT99]. By known bounds from the load balancing literature [RS98], 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. Thu, 15 Sep 2022 18:25:12 +0300https://eccc.weizmann.ac.il/report/2022/047#revision1
Paper TR22-047
| Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds |
Manik Dhar,
Zeev Dvir
https://eccc.weizmann.ac.il/report/2022/047We 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 variable $L(U_S)$ is close to uniform in the $\ell_\infty$ norm. In other words, every element in the range $\mathbb{F}_q^t$ 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 $\ell_1$, distance (for a richer class of functions) as well as prior work on the expected largest 'bucket size' in linear hash functions [ADMPT99]. 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.Mon, 04 Apr 2022 22:20:29 +0300https://eccc.weizmann.ac.il/report/2022/047