## Pseudorandomness and Average-Case
Complexity via Uniform Reductions

Luca Trevisan and
Salil Vadhan

### Abstract

Impagliazzo and Wigderson (36^{th} 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 ]