The complexity of constructing pseudorandom generators from hard functions

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) --> {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(epsilonl) fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a PRG : {0, 1}(O(log n)) --> {0, 1}(n) computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies BP (.) 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) --> {0, 1} ( i. e. there is a constant epsilon > 0 such that every circuit of size 2(epsilonl) fails to compute f on some input) for every positive constant delta < 1 there is no black-box construction of a PRG : {0, 1}(deltan) --> {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 black-box worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomial-size constant-depth circuits cannot compute good extractors and list-decodable codes.