<p>Let <span class="math-container">$m = 1 + \log \ell$</span>. Identify a hash function <span class="math-container">$h \colon \{0, 1\}^k \to \{0, 1\}^m$</span> with its <span class="math-container">$n$</span>-bit truth table <span class="math-container">$h \in \{0, 1\}^n$</span> where <span class="math-container">$n = m \cdot 2^k$</span>. Our hash family <span class="math-container">$\mathcal{H} \subseteq \{0, 1\}^n$</span> consists of an <a href="https://en.wikipedia.org/wiki/Small-bias_sample_space#%CF%B5-biased_set" rel="nofollow noreferrer"><span class="math-container">$\varepsilon$</span>-biased set</a> for a suitable <span class="math-container">$\varepsilon = \ell^{-\Theta(k)}$</span>. Explicit constructions of such a hash family are known with
<span class="math-container">$$
\log |\mathcal{H}| = O(\log(n/\varepsilon)) = O(k \log \ell) = O(k \log k).
$$</span>
See e.g. <a href="https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240030308" rel="nofollow noreferrer">this paper</a>.</p>
<p>To prove that this works, fix any <span class="math-container">$\vec{x} = (x_1, \dots, x_{\ell}) \in \mathcal{S}$</span>. Let <span class="math-container">$f_{\vec{x}} \colon \{0, 1\}^n \to \{0, 1\}$</span> be the function indicating whether there is a collision on the last hash, i.e.,
<span class="math-container">$$
f_{\vec{x}}(h) = \bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq h(x_{\ell})).
$$</span>
We will show that <span class="math-container">$\mathcal{H}$</span> fools this function, i.e., <span class="math-container">$|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr[f_{\vec{x}}(U_n) = 1]| \leq 2^{-k}$</span>. Conditions 1 and 2 will follow.</p>
<p>For each <span class="math-container">$z \in \{0, 1\}^m$</span>, define <span class="math-container">$f_{\vec{x}}^{(z)} \colon \{0, 1\}^n \to \{0, 1\}$</span> by
<span class="math-container">$$
f_{\vec{x}}^{(z)}(h) = \left(\bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq z)\right) \wedge (h(x_{\ell}) = z).
$$</span>
For a fixed <span class="math-container">$z$</span>, the function <span class="math-container">$f_{\vec{x}}^{(z)}$</span> can be computed by a <em>read-once CNF</em> with <span class="math-container">$\ell-1+m=O(\ell)$</span> clauses that reads the bits of the truth table of <span class="math-container">$h$</span>. For a suitable <span class="math-container">$\varepsilon = \ell^{-O(\log(1/\delta))}$</span>, an <span class="math-container">$\epsilon$</span>-biased distribution fools such read-once CNFs with error <span class="math-container">$\delta$</span> -- see <a href="https://link.springer.com/chapter/10.1007/978-3-642-15369-3_38" rel="nofollow noreferrer">this paper</a>. Therefore, <span class="math-container">$\mathcal{H}$</span> fools <span class="math-container">$f_{\vec{x}}^{(z)}$</span> with error <span class="math-container">$\delta$</span>. Now, <span class="math-container">$f_{\vec{x}} = \sum_z f_{\vec{x}}^{(z)}$</span>, so by the triangle inequality, <span class="math-container">$\mathcal{H}$</span> fools <span class="math-container">$f_{\vec{x}}$</span> with error <span class="math-container">$\delta \cdot 2^m$</span>. Choosing <span class="math-container">$\delta = 2^{-k - m}$</span>, we have <span class="math-container">$\varepsilon = \ell^{-O(k + m)} = \ell^{-O(k)}$</span> as promised.</p>
<p>Now let's see how conditions 1 and 2 follow. For any <span class="math-container">$\vec{x} \in \mathcal{S}$</span>, we have <span class="math-container">$\Pr[f_{\vec{x}}(U_n) = 1] = (1 - 2^{-m})^{\ell - 1}$</span>. This value is independent of <span class="math-container">$\vec{x}$</span>, and it changes by at most <span class="math-container">$2^{-k}$</span> when we use <span class="math-container">$\mathcal{H}$</span> instead of <span class="math-container">$U_n$</span>, so for every two <span class="math-container">$\vec{x}, \vec{x}' \in \mathcal{S}$</span>, we have <span class="math-container">$|\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}$</span>, verifying condition 1. Meanwhile, by the union bound, <span class="math-container">$\Pr[f_{\vec{x}}(U_n) = 0] \leq \ell 2^{-m} \leq 1/2$</span>. Again, when we switch to <span class="math-container">$\mathcal{H}$</span>, this value increases by at most <span class="math-container">$2^{-k}$</span>, verifying condition 2.</p>

CC BY-SA 4.0
2021-04-30T05:00:32.270Z
2021-04-30T06:33:12.073Z
2021-04-30T06:33:12.073Z
William Hoza
<p>I am looking for a family of functions that has similar properties to a family of <span class="math-container">$\ell$</span>-wise independent hash functions. The goal is to hash <span class="math-container">$\ell$</span> pairwise different bit strings of length <span class="math-container">$k$</span> to a set of size <span class="math-container">$\approx \ell$</span> such that the probability for the last hash value to collide with any former hash value is almost identical for all possible inputs.</p>

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

<p>The question then is whether there is a family of functions <span class="math-container">$ \mathcal{H} := \{h : \{0,1\}^k \to \{0,1\}^m\} $</span>, for some <span class="math-container">$m = \mathcal{O}(\log(\ell))$</span> such that</p>

<ol>
<li><p>the upper and lower bounds on a collision for the last hash are almost identical, meaning
<span class="math-container">$$
\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)}
$$</span></p></li>
<li><p>and there is some constant <span class="math-container">$c \in (0,1]$</span>, such that
<span class="math-container">$$
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})]
\},
$$</span>
independently from <span class="math-container">$k$</span> and <span class="math-container">$\ell$</span>.</p></li>
<li>Furthermore, a function in <span class="math-container">$\mathcal{H}$</span> should be representable by <span class="math-container">$\mathcal{O}(k \log(k))$</span> many bits.</li>
</ol>

<p>While a family of (almost) <span class="math-container">$\ell$</span>-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 <span class="math-container">$\Omega(\ell)$</span> many bits to represent a function from the family.</p>

<p>There is already <a href="https://cstheory.stackexchange.com/questions/36630/notion-similar-to-k-wise-independence">this</a> 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 <span class="math-container">$k$</span>-wise independence suffices to achieve results very close to full independence:</p>

<p><em>Schmidt, Jeanette P.; Siegel, Alan; Srinivasan, Aravind</em>, <a href="http://dx.doi.org/10.1137/S089548019223872X" rel="nofollow noreferrer"><strong>Chernoff-Hoeffding bounds for applications with limited independence</strong></a>, SIAM J. Discrete Math. 8, No. 2, 223-250 (1995). <a href="https://zbmath.org/?q=an:0819.60032" rel="nofollow noreferrer">ZBL0819.60032</a>.</p>

<p><em>Dietzfelbinger, Martin; Rink, Michael</em>, <a href="http://dx.doi.org/10.1007/978-3-642-02927-1_30" rel="nofollow noreferrer"><strong>Applications of a splitting trick</strong></a>, 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). <a href="https://zbmath.org/?q=an:1248.68166" rel="nofollow noreferrer">ZBL1248.68166</a>.</p>

<p><em>Celis, L. Elisa; Reingold, Omer; Segev, Gil; Wieder, Udi</em>, <a href="http://dx.doi.org/10.1137/120871626" rel="nofollow noreferrer"><strong>Balls and bins: smaller hash families and faster evaluation</strong></a>, SIAM J. Comput. 42, No. 3, 1030-1050 (2013). <a href="https://zbmath.org/?q=an:1275.68075" rel="nofollow noreferrer">ZBL1275.68075</a>.</p>

<p>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.</p>

<derandomization><hash-function><space-complexity><independence><k-wise-independence>
Family of functions with properties similar to k-wise independent hash functions
Dave
# Family of functions with properties similar to k-wise independent hash functions

(Asked by: username_0 on 2020-02-07)

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](https://cstheory.stackexchange.com/questions/36630/notion-similar-to-k-wise-independence) 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**](http://dx.doi.org/10.1137/S089548019223872X), SIAM J. Discrete Math. 8, No. 2, 223-250 (1995). [ZBL0819.60032](https://zbmath.org/?q=an:0819.60032).

*Dietzfelbinger, Martin; Rink, Michael*, [**Applications of a splitting trick**](http://dx.doi.org/10.1007/978-3-642-02927-1_30), 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](https://zbmath.org/?q=an:1248.68166).

*Celis, L. Elisa; Reingold, Omer; Segev, Gil; Wieder, Udi*, [**Balls and bins: smaller hash families and faster evaluation**](http://dx.doi.org/10.1137/120871626), SIAM J. Comput. 42, No. 3, 1030-1050 (2013). [ZBL1275.68075](https://zbmath.org/?q=an:1275.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.

**Tags:** derandomization, hash-function, space-complexity, independence, k-wise-independence


---

## 1 answers

### Answer by username_1 on 2021-04-30. Score: 2

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](https://en.wikipedia.org/wiki/Small-bias_sample_space#%CF%B5-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](https://onlinelibrary.wiley.com/doi/abs/10.1002/rsa.3240030308).

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](https://link.springer.com/chapter/10.1007/978-3-642-15369-3_38). 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.


---

