Pseudorandomness and Average-Case Complexity via Uniform Reductions

Luca Trevisan and Salil Vadhan


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:

  1. 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)}.
  2. 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.
  3. 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


[ back to Salil Vadhan's research interests ]