The Complexity of Constructing Pseudorandom Generators from Hard Functions¤ (Preliminary Version)

We study the complexity of building pseudorandom generators (PRGs) from hard functions. We show that, starting from a function f: f0; 1gl! f0; 1g that is mildly hard on average, i.e. every circuit of size 2(l) fails to compute f on at least a 1=poly(l) fraction of inputs, we can build a PRG: f0; 1gO(logn)! f0; 1gn computable in ATIME (O(1); log n) = alternating time O(logn) with O(1) alternations. Such a PRG implies BP ¢AC0 = AC0 under DLOGTIME-uniformity. On the negative side, we prove a tight time-alternations tradeoff for black-box PRG constructions that are based on worst-case hard functions. We also prove a tight time-alternations tradeoff for black-box worst-case hardness amplification, which is the problem of producing an average-case hard function starting from a worst-case hard one. In particular, we obtain that there is no black-box worst-case hardness amplification within the polynomial time hierarchy. These lower bounds are obtained by showing that constant depth circuits cannot compute extractors and list-decodable codes. 1