Linear Hashing with l8guarantees and two-sided Kakeya bounds

Manik Dhar, Zeev Dvir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show that a randomly chosen linear map over a finite field gives a good hash function in the l8 sense. More concretely, consider a set S ? Fqn and a randomly chosen linear L: Fqn Fqt with qt taken to be sufficiently smaller than |S|. Let US 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(US) is close to uniform in the l8 norm. In other words, every element in the range Fqt 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 l1, distance (for a richer class of functions) as well as prior work on the expected largest 'bucket size' in linear hash functions [1]. By known bounds from the load balancing literature [2], 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.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PublisherIEEE Computer Society
Pages419-428
Number of pages10
ISBN (Electronic)9781665455190
DOIs
StatePublished - 2022
Externally publishedYes
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: Oct 31 2022Nov 3 2022

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2022-October
ISSN (Print)0272-5428

Conference

Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States
CityDenver
Period10/31/2211/3/22

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Hashing
  • Kakeya
  • Leftover Hash Lemma
  • Polynomial Method

Fingerprint

Dive into the research topics of 'Linear Hashing with l8guarantees and two-sided Kakeya bounds'. Together they form a unique fingerprint.

Cite this