I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a set of size $\approx \ell$ such that the probability for the last hash value to collide with any former hash value is almost identical for all possible inputs.

More formally, let $k, \ell \in \mathbb{N}$, where $\ell \gg k$ is polynomial in $k$. Now let $\mathcal{S} := \{(x_1, \ldots, x_{\ell}) \in (\{0,1\}^k)^\ell \text{ with } x_i \neq x_j \forall i \neq j\}$ be the set of all sequences of length $\ell$ of pairwise different elements from $\{0,1\}^k$.

The question then is whether there is a family of functions $ \mathcal{H} := \{h : \{0,1\}^k \to \{0,1\}^m\} $, for some $m = \mathcal{O}(\log(\ell))$ such that

  1. the upper and lower bounds on a collision for the last hash are almost identical, meaning $$ \max_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})]\} - \min_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})] \} \leq 2^{\Omega(k)} $$

  2. and there is some constant $c \in (0,1]$, such that $$ c \leq \min_{(x_1, \ldots, x_{\ell}) \in \mathcal{S}}\{ \Pr_{h \in \mathcal{H}}[\forall i \in [\ell-1]: h(x_i) \neq h(x_{\ell})] \}, $$ independently from $k$ and $\ell$.

  3. Furthermore, a function in $\mathcal{H}$ should be representable by $\mathcal{O}(k \log(k))$ many bits.

While a family of (almost) $\ell$-wise independent hash functions would fulfill conditions 1 and 2, all such families I am aware of would not fulfill condition 3 since they require at least $\Omega(\ell)$ many bits to represent a function from the family.

There is already this question on this Stackexchange, but it is only concerned with the lower bound and the size of the representation, not with the difference between upper and lower bound. There are also several publications that show that in many cases $k$-wise independence suffices to achieve results very close to full independence:

Schmidt, Jeanette P.; Siegel, Alan; Srinivasan, Aravind, Chernoff-Hoeffding bounds for applications with limited independence, SIAM J. Discrete Math. 8, No. 2, 223-250 (1995). ZBL0819.60032.

Dietzfelbinger, Martin; Rink, Michael, Applications of a splitting trick, Albers, Susanne (ed.) et al., Automata, languages and programming. 36th international colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-02926-4/pbk). Lecture Notes in Computer Science 5555, 354-365 (2009). ZBL1248.68166.

Celis, L. Elisa; Reingold, Omer; Segev, Gil; Wieder, Udi, Balls and bins: smaller hash families and faster evaluation, SIAM J. Comput. 42, No. 3, 1030-1050 (2013). ZBL1275.68075.

However, the publications mostly consider the probability in a balls into bins experiment for the maximal load of a bin to be greater than a threshold. While there is some similarity between the two questions, I fail to preciesly map my question to the maximum load of a bin.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.