# Connection between Pseudo random generators and hardness

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

• What is $S'(l)Prg$? Which theorem or lemma in [Nisan Wigderson 1988] implies "if there exists $f\in E$ with $H_{avg}(f)\ge S(n)$ then there is a $S'(l)Prg$ where $S'(l)=S(n)^{0.01}$"? – xskxzr Nov 11 '20 at 11:02
• " For any general $S(l)$, a Pseudo-random generator, is called an $S(l)-Prg$ if for circuit family $C_n$ of size $S(l)$ $|Pr_{x\in G}[C_n(x)=1]-Pr_{x\in U_n}[C_n(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$." - This is what I know about $S(l)-prg$. There was a result like this in NIsan Wigderson 1988, but what I asked over here is independent of that. It comes from the definitions and some probability trick, I think.. – roydiptajit Nov 11 '20 at 14:06
• You seem to refer to Theorem 1 in [Nisan Wigderson 1988], but the original theorem does not mention 0.01. Where is the 0.01 comes from? – xskxzr Nov 11 '20 at 14:57
• And Theorem 1 in [Nisan Wigderson 1988] states that the two parts are equivalent. Is that what you want? – xskxzr Nov 11 '20 at 14:58
• I cannot give you the details of the paper, I am sorry, as I did not go through it. All this I got from my university lecture materials. I just want to know if $\exists\;f$, s.t. $S(l)-prg->H_{avg}(f)\geq S((n)$. Definitions are all according to above, might be confusing, that is why I am also struggling with it. What I think is it does not have any connection with NW 1988. – roydiptajit Nov 11 '20 at 15:53

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].