Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-020 | 8th March 2004 00:00

The Complexity of Constructing Pseudorandom Generators from Hard Functions



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.

ISSN 1433-8092 | Imprint