Emanuele Viola

We study pseudorandom generator (PRG) constructions $G^f : {0,1}^l \to {0,1}^{l+s}$ from one-way functions $f : {0,1}^n \to {0,1}^m$. We consider PRG constructions of the form $G^f(x) = C(f(q_{1}) \ldots f(q_{poly(n)}))$

where $C$ is a polynomial-size constant depth circuit

and $C$ and the $q$'s are generated from $x$ arbitrarily.

more >>>