Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-056 | 20th July 2000 00:00

On Pseudorandomness with respect to Deterministic Observers.



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.

ISSN 1433-8092 | Imprint