Emanuele Viola

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

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