<p>You can do it with the <a href="https://en.wikipedia.org/wiki/Isolation_lemma" rel="nofollow">isolation lemma</a>. Here are the important details (admittedly hastily written):</p>

<p>We'll imagine picking a hash function from $H$ as follows: first, pick $w_1^0,\ldots,w_n^0,w_1^1,\ldots,w_n^1$ uniformly and independently from  integer weights in $[1,4n]$. Then pick a threshold $T$ in $[1,4n^2]$ also uniformly and independently at random. Let $w(x) = \sum_i x_iw_i^1 + (1-x_i)w_i^0$. Now define $h(x)$ to be one if $w(x) \le T$ and zero otherwise.</p>

<p>We can then lower-bound the probability you're interested in by
$$\begin{align*}
P_{h\gets H}[ h(x_2) = \cdots = h(x_{n^k}) = 0, h(x_1) = 1 ] \\
&amp;\ge P_{h \gets H}[ \forall i &gt; 1 : w(x_1) &lt; w(x_i), T = w(x_1) ] \\
&amp;= P_{h \gets H}[ \forall i &gt; 1 : w(x_1) &lt; w(x_i) ] \cdot P_{h\gets H}[ w(x_1) = T \mid \forall i &gt; 1 : w(x_1) &lt; w(x_i) ]
\end{align*}$$
which is to say that $x_1$ is the unique minimum-weight element, and $T$ equals $w(x_1)$. We can easily compute the right factor
using the uniformity and independence of $T$:
$$P_{h\gets H}[ w(x_1) = T \mid \forall i &gt; 1: w(x_1) &lt; w(x_i) ] = \frac{1}{4n^2}$$
Bounding the other factor will involve the isolation lemma. The lemma tells us that
$$P_{h \gets H}[\exists j \forall i\ne j : w(x_j) &lt; w(x_i)] \ge 1-\frac{2n}{4n} = \frac{1}{2}$$
By a union bound, the left hand side is at most
$$\sum_{j=1}^{n^k} P_{h \gets H}[\forall i\ne j: w(x_j) &lt; w(x_i)]$$
From here, observe that the distribution of $w(x)$ doesn't depend on $x$. Hence, the terms in the above sum are all identical (they don't depend on $j$). Combining with the previous inequality and rearranging, we thus have
$$P_{h \gets H}[\forall i &gt; 1 : w(x_1) &lt; w(x_i)] \ge \frac{1}{2n^k}$$
Plugging this into our earlier work, we conclude
$$P_{h\gets H}[ h(x_2) = \cdots = h(x_{n^k}) = 0, h(x_1) = 1 ] \ge \frac{1}{8n^{k+2}}$$
Lastly, each $h$ can be computed very easily: a fixed $h$ needs $O(n\log(n))$ bits to store the $w_i^b$ and $T$, and then some circuitry to sum the appropriate weights and compare against $T$.</p>

CC BY-SA 3.0
2016-09-21T05:55:33.897Z
2016-09-21T06:20:46.963Z
2016-09-21T06:20:46.963Z
Andrew Morgan
<p>I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ be some large natural number that is fixed. There exists a $d$ such that for every $n^k$ tuple of $n$ bit strings $x_1,...,x_{n^k}$,</p>

<p>$Pr_{h \leftarrow H}[  \cap_{j=2}^{n^k}  h(x_j)=0 \, \cap \, h(x_1)=1] \geq 1/n^d$  </p>

<p>The additional (and crucial constraint) is that I want to be able to compute this family of functions using (a family of) circuits of size at most $n^3$ ($k$ is much bigger than 3). Note that if we don't have this constraint, then it is possible to do this (using family of circuits of size at least $n^e$). </p>

<p>Is it even possible for such a family to exist? </p>

<cc.complexity-theory><derandomization><hash-function><independence><k-wise-independence>
Notion similar to k-wise independence
NotSo Smart
# Notion similar to k-wise independence

(Asked by: username_0 on 2016-09-21)

I want to construct a family of functions $H:\{0,1\}^n \rightarrow \{0,1\}$ with a property that is similar to k-wise independence. Specifically, I want $H$ to satisfy the following property. Let $k$ be some large natural number that is fixed. There exists a $d$ such that for every $n^k$ tuple of $n$ bit strings $x\_1,...,x\_{n^k}$,

$Pr\_{h \leftarrow H}[ \cap\_{j=2}^{n^k} h(x\_j)=0 \, \cap \, h(x\_1)=1] \geq 1/n^d$

The additional (and crucial constraint) is that I want to be able to compute this family of functions using (a family of) circuits of size at most $n^3$ ($k$ is much bigger than 3). Note that if we don't have this constraint, then it is possible to do this (using family of circuits of size at least $n^e$).

Is it even possible for such a family to exist?

**Tags:** cc.complexity-theory, derandomization, hash-function, independence, k-wise-independence

---

## 1 answers

### Answer by username_1 on 2016-09-21. Score: 2

You can do it with the [isolation lemma](https://en.wikipedia.org/wiki/Isolation_lemma). Here are the important details (admittedly hastily written):

We'll imagine picking a hash function from $H$ as follows: first, pick $w\_1^0,\ldots,w\_n^0,w\_1^1,\ldots,w\_n^1$ uniformly and independently from integer weights in $[1,4n]$. Then pick a threshold $T$ in $[1,4n^2]$ also uniformly and independently at random. Let $w(x) = \sum\_i x\_iw\_i^1 + (1-x\_i)w\_i^0$. Now define $h(x)$ to be one if $w(x) \le T$ and zero otherwise.

We can then lower-bound the probability you're interested in by
$$\begin{align\*}
P\_{h\gets H}[ h(x\_2) = \cdots = h(x\_{n^k}) = 0, h(x\_1) = 1 ] \\
&\ge P\_{h \gets H}[ \forall i > 1 : w(x\_1) < w(x\_i), T = w(x\_1) ] \\
&= P\_{h \gets H}[ \forall i > 1 : w(x\_1) < w(x\_i) ] \cdot P\_{h\gets H}[ w(x\_1) = T \mid \forall i > 1 : w(x\_1) < w(x\_i) ]
\end{align\*}$$
which is to say that $x\_1$ is the unique minimum-weight element, and $T$ equals $w(x\_1)$. We can easily compute the right factor
using the uniformity and independence of $T$:
$$P\_{h\gets H}[ w(x\_1) = T \mid \forall i > 1: w(x\_1) < w(x\_i) ] = \frac{1}{4n^2}$$
Bounding the other factor will involve the isolation lemma. The lemma tells us that
$$P\_{h \gets H}[\exists j \forall i\ne j : w(x\_j) < w(x\_i)] \ge 1-\frac{2n}{4n} = \frac{1}{2}$$
By a union bound, the left hand side is at most
$$\sum\_{j=1}^{n^k} P\_{h \gets H}[\forall i\ne j: w(x\_j) < w(x\_i)]$$
From here, observe that the distribution of $w(x)$ doesn't depend on $x$. Hence, the terms in the above sum are all identical (they don't depend on $j$). Combining with the previous inequality and rearranging, we thus have
$$P\_{h \gets H}[\forall i > 1 : w(x\_1) < w(x\_i)] \ge \frac{1}{2n^k}$$
Plugging this into our earlier work, we conclude
$$P\_{h\gets H}[ h(x\_2) = \cdots = h(x\_{n^k}) = 0, h(x\_1) = 1 ] \ge \frac{1}{8n^{k+2}}$$
Lastly, each $h$ can be computed very easily: a fixed $h$ needs $O(n\log(n))$ bits to store the $w\_i^b$ and $T$, and then some circuitry to sum the appropriate weights and compare against $T$.


---

