Let \(\varepsilon\) be a small absolute constant, say \(\varepsilon=1/1000\).

Let \(f\colon \{\pm1\}^n \to \{\pm1\}\) be a strongly average-case hard function, that is, \(\mathbb E f\cdot C\le 1/2^{\varepsilon n}\) for all circuits \(C\colon \{\pm1\}^n\to\{\pm1\}\) with \(\mathrm{size}(C)\le 2^{\varepsilon n}\).

For \(\sigma=O(n)\), let \(S_1,\ldots,S_m\) be equal-sized subsets of \(\{1,\ldots,\sigma\}\) with \(m=2^{\Omega(\sigma)}\) and \(|S_i\cap S_j|\ll 0.1\varepsilon|S_i|=n\). (Such set systems exist and can be computed in \(\mathrm{poly}(m)\)-time.) We also assume \(m\le 2^{0.1\varepsilon n}\) (which can be arranged easily by discarding sets).

Theorem: The distribution \(G(U_\sigma)\) with \(G(x) = (f(x_{S_1}),\ldots,f(x_{S_m}))\) fools circuits of size \(2^{\Omega(\sigma)}\) with error \(0.1\).

Proof:

We prove the contrapositive. Suppose the generated distribution is not pseudorandom in the sense above. Then there exists a circuit \(C\colon \{\pm1\}^k\to\{\pm1\}\) with \(\mathrm{size}(C)\le 2^{o(n)}\) that predicts one of the bits of the distribution, \[ \mathbb E C(f(x_{S_1}),\ldots,f(x_{S_k}))\cdot f(x_{S_{k+1}})\ge 1/10m. \]

We want to show that this circuit implies that the function \(f\) is not strongly average-case hard (in the sense above).

We split the inputs of the functions according to the set \(T=S_{k+1}\). Let \(T_i=S_i\cap S\) and let \(R_i=S_i\cap R\) for \(R=\bar T\). Then, \[ \mathbb E_{x_{R}} \mathbb E_{x_T} C(f(x_{R_1},x_{T_1}),\ldots,f(x_{R_k},x_{T_k}))\cdot f(x_{T})\ge 1/10m. \] In particular, there exists a string \(x^*_R\) such that \[ \mathbb E_{x_T} C(f(x^*_{R_1},x_{T_1}),\ldots,f(x^*_{R_k},x_{T_k}))\cdot f(x_{T})\ge 1/10m. \]

Since \(|T_i|=|S_i\cap S_{k+1}|\le 0.1\varepsilon n\), the functions \(x_{T_i}\mapsto f(x^*_{R_i},x_{T_i})\) have circuits \(C_i\) of size \(2^{0.1\varepsilon n}\). It follows that the circuit \(C(C_1(\cdot),\ldots,C_m(\cdot))\) has size \(2^{o(n)}+m\cdot 2^{0.1\varepsilon n}<2^{\varepsilon n}\) and computes \(f\) with advantage at least \(10/m\ge 2^{-\varepsilon n}\). Thus, \(f\) is not strongly average-case hard.

Remark: If we have a collection of strongly average-case hard functions \(\{f_n\}\) for all input sizes that can be computed (by a Turing machine) in exponential time, then the generator above allows us to derandomize BPP, so that P=BPP.