0
$\begingroup$

How to show that for $\epsilon>0$, there exists a function $G:\{0,1\}^n->\{0,1\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. What I am trying to show is with high probability, if we take $\epsilon=1/10$, a random $G$ satisfies this condition. But in order to show that, we need to show, no circuits of size $<2^{3/10n}$ are able to distinguish between uniform distribution of length $2^{n/10}$ and output of $G$. This I am not able to get. Can anyone give me an approach?

$\endgroup$
0
$\begingroup$

If you choose $G$ from the uniform random distribution on $\{0, 1\}^n \to \{0, 1\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it is random.

$\endgroup$
2
  • $\begingroup$ But how to prove the statement in terms of the definition of pseudorandom generators? Also how to use $\epsilon=1/10$? The question is given in arora barrak Computational Complexity, chapt 16 ex-2 $\endgroup$ – roydiptajit Nov 4 '20 at 16:39
  • $\begingroup$ @DiptajitRoy I'm sorry, I don't know. Your approach where you choose $G$ to be random doesn't work though, no matter what, due to the reason in my answer, I'm assuming that wasn't part of the original question. $\endgroup$ – orlp Nov 10 '20 at 18:20

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.