Abstract
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,{m1}}) 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..m1] 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
@InProceedings{dietzfelbinger:LIPIcs.ESA.2023.1,
author = {Dietzfelbinger, Martin},
title = {{On Hashing by (Random) Equations}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {1:11:1},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772952},
ISSN = {18688969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and FarachColton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18654},
URN = {urn:nbn:de:0030drops186545},
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 