Pseudorandomness and Average-Case
Complexity via Uniform Reductions
Luca Trevisan and
Salil Vadhan
Abstract
Impagliazzo and Wigderson (36th FOCS, 1998) gave the first
construction of pseudorandom generators from a *uniform* complexity assumption
on EXP (namely EXP\neq BPP). Unlike results in the nonuniform setting, their
result does not provide a continuous trade-off between worst-case hardness and
pseudorandomness, nor does it explicitly establish an average-case hardness
result.
In this paper:
- We obtain an optimal
worst-case to average-case connection for EXP: if EXP is not a
subset of BPTIME(t(n)), EXP has problems that cannot be solved on a
fraction 1/2 +1/t'(n) of the inputs by BPTIME(t'(n)) algorithms, for
t'=t^{\Omega(1)}.
- We exhibit a PSPACE-complete
self-correctible and downward self-reducible problem. This slightly
simplifies and strengthens the proof of Impaglaizzo and Wigderson, which
used a a #P-complete problem with these properties.
- We argue that the results of
Impagliazzo and Wigderson, and the ones in this paper, cannot be proved
via "black-box" uniform reductions.
Keywords: Pseudorandomness,
Average-case Complexity, Derandomization, Instance Checkers
Versions
- In Proceedings of 17th
Conference on Computational Complexity, Montréal, Québec, May 21-24,
2002. IEEE. [official
IEEE page]
- Full version, January 2006. [ps][pdf]
- Computational Complexity 16(4):331-364, December 2007. [ps][pdf][cc page]
[
back to Salil Vadhan's research interests ]