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

DOI10.46298/THEORETICS.24.8arXiv2204.01665MaRDI QIDQ6505692FDOQ6505692

Abstract: We show that a randomly chosen linear map over a finite field gives a good hash function in the

e l l_{i} n f t y

sense. More concretely, consider a set

S s u b s e t m a t h b b F_{q}^{n}

and a randomly chosen linear map

L : m a t h b b F_{q}^{n} o m a t h b b 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

e l l_{i} n f t y

norm. In other words, {em every} element in the range

m a t h b b 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

e l l_{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 trully 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.

This page was built for publication: Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505692)