Notion similar to k-wise independence

Question

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?

Answer 1

You can do it with the 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$.