1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ 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}$"? $\endgroup$
    – xskxzr
    Nov 11 '20 at 11:02
  • $\begingroup$ " 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.. $\endgroup$ Nov 11 '20 at 14:06
  • $\begingroup$ 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? $\endgroup$
    – xskxzr
    Nov 11 '20 at 14:57
  • $\begingroup$ And Theorem 1 in [Nisan Wigderson 1988] states that the two parts are equivalent. Is that what you want? $\endgroup$
    – xskxzr
    Nov 11 '20 at 14:58
  • $\begingroup$ 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. $\endgroup$ Nov 11 '20 at 15:53
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.