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?


1 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.