Connection between Pseudo random generators and hardness

Question

For a boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ $H_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C_n$ of size $S(n)$, $\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $U_n$ is uniform distribution over $\{0,1\}^n$.

According to Nisan Wigderson 1988, I know that if there exists $f\in E$ with $H_{avg}(f)\geq S(n)$ then there is a $S'(l)$-Prg where $S'(l)=S(n)^{0.01}$. For any general $S(l)$, a Pseudo-random generator, is called an $(S(l),\epsilon)$-Prg if for circuit family $C_{S(l)}$ of size $S(l)$ $|Pr_{x\in U_{l}}[C_{S(l)}(G(x))=1]-Pr_{x\in U_{S(l)}}[C_{S(l)}(x)=1]|<\epsilon$. Here $G$ is a pseudo random function $G:\{0,1\}^l\longrightarrow\{0,1\}^{S(l)}$, generates an $S(l)$ length strings from length $l$.

I was thinking if the converse is also true or not. Means, if we can show the existence of $S(l)$-Prg, then does it follows that there is $f$ with $H_{avg}(f)\geq S(n)$?

Answer 1

Theorem 1 in [Nisan Wigderson 1988] implies:

For any function $l\le s(l)\le 2^l$, the following are equivalent:

1. For some $c>0$, there exists a quick PRG $G: l\to s(l^c)$.
2. For some $c>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$.

Although their definition of (quick) PRG and hardness are slightly different from yours, I think the conclusion is still the same (as long as $\epsilon <1/2$, and your conclusion should be $H_{avg}(f)\ge S(l^c)$ for some $c$ rather than $H_{avg}(f)\ge S(n)$).

The proof can be summarized as follows:

1. Regard the PRG as an extender from string of length $l$ to string of length $l+1$, and consider the boolean function $f$ corresponding to this extender.

2. Show that $f$ cannot be approximated by circuits of size $S(l^c)$, i.e., for some constant $k$, all large enough $l$, and all circuits $C_l$ of size $S(l^c)$, $\mathrm{Pr}_{x\in U_l}[C_l(x)\neq f(x)]>n^{-k}$ (note this is a weaker condition compared to the definition of hardness, i.e. your $H_{avg}$).

3. Use Yao's lemma [Yao 1982] to xor multiple copies of $f$ to obtain a function $f'$ such that $H_{avg}(f')\ge S(l^c)$.

You can see more details in [Nisan Wigderson 1988].