ECCC-Report TR00-056https://eccc.weizmann.ac.il/report/2000/056Comments and Revisions published for TR00-056en-usMon, 24 Jul 2000 11:12:37 +0300
Paper TR00-056
| On Pseudorandomness with respect to Deterministic Observers. |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2000/056In 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.
Mon, 24 Jul 2000 11:12:37 +0300https://eccc.weizmann.ac.il/report/2000/056