Notion similar to k-wise independence 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?
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 ] \\
&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$.