TR00-056 Authors: Oded Goldreich, Avi Wigderson

Publication: 24th July 2000 11:12

Downloads: 1062

Keywords:

In the theory of pseudorandomness, potential (uniform) observers

are modeled as probabilistic polynomial-time machines.

In fact many of the central results in

that theory are proven via probabilistic polynomial-time reductions.

In this paper we show that analogous deterministic reductions

are unlikely to hold. We conclude that randomness of the observer

is essential to the theory of pseudorandomness.

What we actually prove is that the hypotheses

of two central theorems (in the theory of pseudorandomness)

hold unconditionally when stated with

respect to deterministic polynomial-time algorithms.

Thus, if these theorems were true for deterministic

observers, then their conclusions would hold

unconditionally, which we consider unlikely.

For example, it would imply (unconditionally)

that any unary language in BPP is in P.

The results are proven using diagonalization and

pairwise independent sample spaces.