Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CONSTANT DEPTH CIRCUIT:
Reports tagged with constant depth circuit:
TR04-020 | 8th March 2004
Emanuele Viola

#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

We study the complexity of building
pseudorandom generators (PRGs) from hard functions.

We show that, starting from a function f : {0,1}^l -> {0,1} that
is mildly hard on average, i.e. every circuit of size 2^Omega(l)
fails to compute f on at least a 1/poly(l)
fraction of inputs, we can ... more >>>

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