I couldn't understand how exactly Yao's XOR lemma was used to prove the following claim made in the proof of Theorem 2 of the original paper describing the Nisan-Wigderson generator, so I decided to do it explicitly myself.

Claim 1: If $f \in EXP$ cannot be approximated by circuits of polynomial size, then for every $0 < \rho < 1$, there is a quick pseudorandom generator $G : n^\rho \rightarrow n$.

In the paper, we say that a function $f : \{0, 1\}^m \rightarrow \{0, 1\}$ cannot be approximated by circuits of size $s : \mathbb{N} \rightarrow \mathbb{N}$ if there exists constant $k_0$ such that for every s-size circuit family ${C_m}$, we have

$$\Pr(C_m(x) \neq f(x)) > \frac{1}{m^{k_0}}$$.

As such, we may rewrite Claim 1 equivalently as follows.

Alternative Claim 1 Suppose there exists $f \in EXP$ such that for all $k \in \mathbb{N}$, there exists constant $k_0$ (which depends on $k$; we denote this by writing $k_0 := k_0(k)$) such that for all $m^k$-size circuit families ${C(m)}$, $\Pr(C_m(x) \neq f(x)) > \frac{1}{m^{k_0(k)}}$. Then for every $0 < \rho < 1$, there is a quick pseudorandom generator $G : n^\rho \rightarrow n$.

The particular version of Yao's XOR Lemma which I use is Levin's version (Lemma 2 here). In the interest of self-containment I recite the relevant statement here as follows. Note that this version is stated in terms of $\{-1, 1\}$ valued functions, but we can simply reinterpret $f$ in the hypothesis of Claim 1 as $(-1)^f$.

Yao's Lemma: Let $f : \{0, 1\}^m \rightarrow \{-1, 1\}$, $s : \mathbb{N} \rightarrow \mathbb{N}$, $\{C_m\}$ be any circuit family of size at most $s$, and $\delta(m)$ be an upper bound on the correlation $\underset{x\in\{0,1\}^m}{\mathbb{E}}[C_m(x) \cdot f(x)]$ between $C_m$ and $f$ such that $|\delta(m)|$ is bounded away from 1 (i.e. $|\delta(m)| \leq 1 - 1/\omega(1)$). Then for any $t : \mathbb{N} \rightarrow \mathbb{N}$ and $\epsilon : \mathbb{N} \rightarrow \mathbb{R}$, let $m' := t(m) \cdot m$ and we have that $\delta^{(t)}(m) := \left( \delta(m) \right)^{t(m)} + \epsilon(m)$ is a bound on the correlation between $f^{(t)} : \{0,1\}^{m'} \rightarrow \{-1, 1\}$ such that $f^{(t)}(x_1x_2...x_{t(m)}) := \prod_{i = 1}^{t(m)}f(x_i)$ (here each $x_i \in \{0, 1\}^m$) and any circuit on $m'$ bits of size at most $s'(m') := (\frac{\epsilon(m)}{m})^{O(1)}s(m) + (m')^{O(1)}$.

After going through the paper, it seems that proving that the Nisan-Wigderson construction for a generator is indeed a quick pseudorandom generator boils down to a constraint satisfaction problem over 4 variables parameterized by the output length $n$ of the generator: $m := m(n)$, the input length of the function $f$ in the hypothesis of Claim 1; $t(m)$, the number of times we XOR $f$ with itself to create the hardness-amplified $f^{(t)}$ in Yao's lemma; $\epsilon(m)$ as in Yao's lemma; and $k$ as in the alternative statement of Claim 1 above (note that here $m^k$ is $s(m)$ in Yao's lemma). The constraints we must satisfy are as follows.

(1) $2^{O(m(n))} \cdot t(m(n)) \cdot n = 2^{O(n^\rho)}$

This constraint comes from the requirement that our generator needs to be quick. A generator G : $n^{l(n)} \rightarrow n$ is called quick if the generator runs in time $2^{O(l(n))}$, and here $l(n) = n^\rho$. To see that the left hand side of this constraint bounds the run time of the Nisan-Wigderson generator, note that the Nisan-Wigderson generator outputs the concatenation of $n$ calls to $f^{(t)}$, where each call of $f^{(t)}$ takes the XOR of $t(m(n))$ evaluations of $f \in EXP$.

(2) $n \geq m'(n) = \Omega(n^\frac{\rho}{2})$, where recall $m'(n) := t(m(n)) \cdot m(n)$ is the input length of the hardness-amplified function $f^{(t)}$.

This requirement ensures that there exists a $(\log(n), m'(n))$-design by Lemma 2.5 in the paper. The existence of such a design is a prerequisite for the proof that the NW Generator is indeed pseudorandom (Lemma 2.4 in the paper).

(3) $\delta^{(t)}(m(n)) \leq \frac{2}{n^2}$

(4) $s'(m'(n)) \geq n^2$

Constraints (3) and (4) above come from the fact that the Nisan-Wigderson generator requires that its basis function ($f^{(t)}$ here) has hardness at least $n^2$ for it to be pseudorandom (again, see Lemma 2.4 in the paper), or in other words, that for all circuits ${C_{m'}}$ (here $m' := m'(n)$) of size at most $n^2$, we have $|\Pr(C_{m'}(x) = f^{(t)}(x)) - \frac{1}{2}| \leq \frac{1}{n^2}$. Constraints (3) and (4) guarantee that we amplify the hardness of $f$ in Yao's lemma enough to satisfy this requirement.

My Question: How is the assumption that $f \in EXP$ cannot be approximated by polynomial size circuits sufficient to guarantee that both constraints (3) and (4) above are satisfied?

I will elaborate my question as follows. Expanding constraint (4) gives

$s'(m'(n)) := (\frac{\epsilon(m(n))}{m(n)})^{O(1)}(m(n))^k - (t(m(n)) \cdot m(n))^{O(1)} > n^2$

Note that in order to satisfy (4), an obviously necessary condition is that $(m(n))^k > t(m(n))$ for all sufficiently large $n$. In other words, it must be that

(5) $$t(m(n)) = O((m(n)^k)$$

otherwise it is impossible for us to choose $k$ large enough for (4) to hold. We now exhibit an asymptotic lower bound on $t(m)$. Since $1 - x \geq e^{-\frac{x}{1 - x}}$ for all $x < 1$, we have that

$$(\delta(m(n)))^{t(m(n))} = (1 - \frac{2}{(m(n))^{k_0}})^{t(m(n))} \geq \exp\left(-\frac{\frac{2t(m(n))}{(m(n))^{k_0}}}{1 - \frac{2}{(m(n))^{k_0}}}\right)$$

and thus a necessary condition for condition (3) to hold (where we let $m := m(n)$) is that

$$ \exp\left(-\frac{\frac{2t(m)}{m^{k_0}}}{1 - \frac{2}{m^{k_0}}}\right) < \frac{2}{n^2} $$

from which we obtain:

$$-\frac{\frac{2t(m)}{m^{k_0}}}{1 - \frac{2}{m^{k_0}}} < \ln(\frac{2}{n^2})$$

Rearranging gives,

$$\frac{\frac{t(m)}{m^{k_0}}}{1 - \frac{2}{m^{k_0}}} > \ln(n) - \frac{1}{2}\ln(2)$$


$${\frac{t(m)}{m^{k_0}}} = \Omega(\ln(n))$$

which necessitates

(6) $$t(m) = \Omega(m^{k_0})$$

Together, (5) and (6) tell us in order for the desired hardness amplification to be possible it must be that $k \geq k_0$. However, recall that $k_0 := k_0(k)$ depends crucially on our choice of $k$. As I understand it, the hypothesis of claim 1 provides no guarantee that $k_0$ is at most $k$. For all we know it could always be that for any choice of $k$ we make, it is always the case that $k_0 > k$. So how is the hypothesis of Claim 1 sufficient to prove that the Nisan-Wigderson generator is indeed pseudorandom?



Your Answer

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