Skip to main content
edited body
Source Link
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

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. RegardsRegard 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)$$H_{avg}(f')\ge S(l^c)$.

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

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

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

Source Link
xskxzr
  • 7.6k
  • 5
  • 23
  • 47

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