Family of functions with properties similar to k-wise independent hash functions

Question

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.

Answer 1

Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family $\mathcal{H} \subseteq \{0, 1\}^n$ consists of an $\varepsilon$-biased set for a suitable $\varepsilon = \ell^{-\Theta(k)}$. Explicit constructions of such a hash family are known with $$ \log |\mathcal{H}| = O(\log(n/\varepsilon)) = O(k \log \ell) = O(k \log k). $$ See e.g. this paper.

To prove that this works, fix any $\vec{x} = (x_1, \dots, x_{\ell}) \in \mathcal{S}$. Let $f_{\vec{x}} \colon \{0, 1\}^n \to \{0, 1\}$ be the function indicating whether there is a collision on the last hash, i.e., $$ f_{\vec{x}}(h) = \bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq h(x_{\ell})). $$ We will show that $\mathcal{H}$ fools this function, i.e., $|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr[f_{\vec{x}}(U_n) = 1]| \leq 2^{-k}$. Conditions 1 and 2 will follow.

For each $z \in \{0, 1\}^m$, define $f_{\vec{x}}^{(z)} \colon \{0, 1\}^n \to \{0, 1\}$ by $$ f_{\vec{x}}^{(z)}(h) = \left(\bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq z)\right) \wedge (h(x_{\ell}) = z). $$ For a fixed $z$, the function $f_{\vec{x}}^{(z)}$ can be computed by a read-once CNF with $\ell-1+m=O(\ell)$ clauses that reads the bits of the truth table of $h$. For a suitable $\varepsilon = \ell^{-O(\log(1/\delta))}$, an $\epsilon$-biased distribution fools such read-once CNFs with error $\delta$ -- see this paper. Therefore, $\mathcal{H}$ fools $f_{\vec{x}}^{(z)}$ with error $\delta$. Now, $f_{\vec{x}} = \sum_z f_{\vec{x}}^{(z)}$, so by the triangle inequality, $\mathcal{H}$ fools $f_{\vec{x}}$ with error $\delta \cdot 2^m$. Choosing $\delta = 2^{-k - m}$, we have $\varepsilon = \ell^{-O(k + m)} = \ell^{-O(k)}$ as promised.

Now let's see how conditions 1 and 2 follow. For any $\vec{x} \in \mathcal{S}$, we have $\Pr[f_{\vec{x}}(U_n) = 1] = (1 - 2^{-m})^{\ell - 1}$. This value is independent of $\vec{x}$, and it changes by at most $2^{-k}$ when we use $\mathcal{H}$ instead of $U_n$, so for every two $\vec{x}, \vec{x}' \in \mathcal{S}$, we have $|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr_{h \in \mathcal{H}}[f_{\vec{x}'}(h) = 1]| \leq 2 \cdot 2^{-k}$, verifying condition 1. Meanwhile, by the union bound, $\Pr[f_{\vec{x}}(U_n) = 0] \leq \ell 2^{-m} \leq 1/2$. Again, when we switch to $\mathcal{H}$, this value increases by at most $2^{-k}$, verifying condition 2.