# Existence of Pseudorandom Generator

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?

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.
• 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 – roydiptajit Nov 4 '20 at 16:39
• @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. – orlp Nov 10 '20 at 18:20