Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > BLACK-BOX CONSTRUCTION:
Reports tagged with black-box construction:
TR04-074 | 26th August 2004
Emanuele Viola

#### On Parallel Pseudorandom Generators

Revisions: 1

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

ISSN 1433-8092 | Imprint