__
TR04-020 | 8th March 2004 00:00
__

#### The Complexity of Constructing Pseudorandom Generators from Hard Functions

**Abstract:**
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 build a PRG : {0,1}^O(log n) -> {0,1}^n

computable in alternating time O(log n) with

O(1) alternations = DLOGTIME-uniform AC_0.

Such a PRG implies BP AC_0 = AC_0 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.