Abstract.
We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function \(f:\{ 0,1\} ^l \to \{ 0,1\} \) computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant \(\epsilon > 0\) such that every circuit of size \(2^{\epsilon l} \) fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a \({\text{PRG}}:\{ 0,1\} ^{O(\log n)} \to \{ 0,1\} ^n \) computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies \(BP \cdot AC^0 = AC^0 \) under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function \(f:\{ 0,1\} ^l \to \{ 0,1\} \) (i.e. there is a constant \(\epsilon > 0\) such that every circuit of size \(2^{\epsilon l} \) fails to compute f on some input) for every positive constant \(\delta < 1\) there is no black-box construction of a \({\text{PRG}}:\{ 0,1\} ^{\delta n} \to \{ 0,1\} ^n \) computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Viola, E. The complexity of constructing pseudorandom generators from hard functions. comput. complex. 13, 147–188 (2005). https://doi.org/10.1007/s00037-004-0187-1
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00037-004-0187-1