License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.1
URN: urn:nbn:de:0030-drops-186545
Go to the corresponding LIPIcs Volume Portal

Dietzfelbinger, Martin

On Hashing by (Random) Equations (Invited Talk)

LIPIcs-ESA-2023-1.pdf (0.4 MB)


The talk will consider aspects of the following setup: Assume for each (key) x from a set š’° (the universe) a vector a_x = (a_{x,0},ā€¦ ,a_{x,{m-1}}) has been chosen. Given a list Z = (z_i)_{i āˆˆ [m]} of vectors in {0,1}^r we obtain a mapping Ļ†_Z: š’° ā†’ {0,1}^r, x ā†¦ āŸØa_x,ZāŸ© := ā؁_{i āˆˆ [m]} a_{x,i} ā‹… z_i, where ā؁ is bitwise XOR. The simplest way for creating a data structure for calculating Ļ†_Z is to store Z in an array Z[0..m-1] and answer a query for x by returning āŸØ a_x,ZāŸ©. The length m of the array should be (1+Īµ)n for some small Īµ, and calculating this inner product should be fast. In the focus of the talk is the case where for all or for most of the sets S āŠ† š’° of a certain size n the vectors a_x, x āˆˆ S, are linearly independent. Choosing Z at random will lead to hash families of various degrees of independence. We will be mostly interested in the case where a_x, x āˆˆ š’° are chosen independently at random from {0,1}^m, according to some distribution š’Ÿ. We wish to construct (static) retrieval data structures, which means that S āŠ‚ š’° and some mapping f: S ā†’ {0,1}^r are given, and the task is to find Z such that the restriction of Ļ†_Z to S is f. For creating such a data structure it is necessary to solve the linear system (a_x)_{x āˆˆ S} ā‹… Z = (f(x))_{x āˆˆ S} for Z. Two problems are central: Under what conditions on m and š’Ÿ can we expect the vectors a_x, x āˆˆ S to be linearly independent, and how can we arrange things so that in this case the system can be solved fast, in particular in time close to linear (in n, assuming a reasonable machine model)? Solutions to these problems, some classical and others that have emerged only in recent years, will be discussed.

BibTeX - Entry

  author =	{Dietzfelbinger, Martin},
  title =	{{On Hashing by (Random) Equations}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-186545},
  doi =		{10.4230/LIPIcs.ESA.2023.1},
  annote =	{Keywords: Hashing, Retrieval, Linear equations, Randomness}

Keywords: Hashing, Retrieval, Linear equations, Randomness
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI