ECCC-Report TR04-020https://eccc.weizmann.ac.il/report/2004/020Comments and Revisions published for TR04-020en-usWed, 24 Mar 2004 00:36:45 +0200
Paper TR04-020
| The Complexity of Constructing Pseudorandom Generators from Hard Functions |
Emanuele Viola
https://eccc.weizmann.ac.il/report/2004/020We 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.
Wed, 24 Mar 2004 00:36:45 +0200https://eccc.weizmann.ac.il/report/2004/020