We study pseudorandom generator (PRG) constructions $G^f \PRGdr$ from one-way functions $f : \zo^n \to \zo^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 (i.e. $\AC$)
and $C$ and the $q$'s are generated from $x$ arbitrarily.
We show that every black-box PRG construction of this form must have stretch $\PRGstretch$ bounded as $\PRGstretch \leq l \cdot ( \log^{O(1)} n) / m + O(1) = o(l)$. This holds even if the PRG construction starts from a one-to-one function $f : \zo^n \to \zo^m$ where $m \geq 5n$.
This shows that either adaptive queries or sequential computation are necessary for black-box PRG constructions with constant factor stretch (i.e. $\PRGstretch = \Omega(l)$) from one-way functions, even if the functions are one-to-one.

On the positive side we show that if there is a one-way function $f : \zo^n \to \zo^m$ that is regular (i.e. the number of preimages of $f(x)$ depends on $|x|$ but not on $x$) and computable by polynomial-size constant depth circuits then there is a PRG $: \zo^l \to \zo^{l+1}$ computable by polynomial-size constant depth circuits. This complements our negative result above because one-to-one functions are regular.

We also study constructions of average-case hard functions starting from worst-case hard ones, i.e. hardness amplifications. We show that if there is an oracle procedure $Amp^f$ in the polynomial time hierarchy ($PH$) such that $Amp^f$ is average-case hard for every worst-case hard $f$, then there is an average-case hard function in $PH$ \emph{unconditionally}.
Bogdanov and Trevisan (FOCS '03) and Viola (CCC'03) show related but incomparable negative results.

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.
We show that every black-box PRG construction of this form must have stretch $s$ bounded as $s \leq l \cdot ( \log^{O(1)} n) / m = o(l)$. This holds even if the PRG construction starts from a one-to-one function $f : {0,1}^n \to {0,1}^m$ where $m \geq 5n$.
This shows that either adaptive queries or sequential computation are necessary for black-box PRG constructions with constant factor stretch (i.e. $s = \Omega(l)$) from one-way functions, even if the functions are one-to-one.

On the positive side we show that if there is a one-way function $f : {0,1}^n \to {0,1}^m$ that is regular (i.e. any $f(x)$ has the same number of preimages) and computable by constant depth circuits then there is a PRG $: {0,1}^l \to {0,1}^{l+1}$ computable by constant depth circuits. This complements our negative result above because one-to-one functions are regular.

We also study constructions of average-case hard functions starting from worst-case hard ones, i.e. hardness amplifications. We show that if there is an oracle procedure $Amp^f$ in the polynomial time hierarchy ($PH$) such that
$Amp^f$ is average-case hard for every worst-case hard $f$, then there is an average-case hard function in $PH$ \emph{unconditionally}.
Bogdanov and Trevisan (FOCS '03) and Viola (CCC'03) show related negative results under incomparable assumptions.
This result is obtained by derandomizing the proof techniques used in our negative result for PRG constructions.