# How is inapproximability by polynomial size circuits sufficient for the Nisan-Wigderson generator?

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)$$

implying,

$${\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?