The Random Oracle Hypothesis is False
 Authors: R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad,
D. Ranjan and P. Rohatgi.
 Cite as:
Journal of Computer and System Sciences,
49(1):2439, August 1994.
 Previous incarnations:
 J. Hartmanis, R. Chang, D. Ranjan and P. Rohatgi.
"Structural Complexity Theory: Recent Surprises."
In Proceedings of the 2nd Scandinavian Workshop
on Algorithm Theory,
SpringerVerlag Lecture Notes in Computer Science #447,
112, July 1990.
 J. Hartmanis, R. Chang, D. Ranjan and P. Rohatgi.
"Structural Complexity Theory: Recent Surprises."
Technical Report 901117, Department of Computer Science,
Cornell University, April 1990.
 B. Chor, O. Goldreich and J. Hastad.
"The Random Oracle Hypothesis is False."
Technical Report 631, Department of Computer Science,
Technion, 1990.
 Most readable version: journal version.
 Status: complete.
 Online:
Abstract:

The Random Oracle Hypothesis, attributed to Bennett and Gill,
essentially states that the relationships between complexity classes
which hold for almost all relativized worlds must also hold in the
unrelativized case. This paper shows that the Random Oracle
Hypothesis is false by showing that for almost all oracles A,
IP(A) is not equal to PSPACE(A). If the Random Oracle
Hypothesis were true, it would contradict Shamir's result that IP =
PSPACE. In fact, it is shown that for almost all oracles A,
coNP(A) is not a subset of IP(A). These results
extend to the multiprover proof systems of BenOr, Goldwasser,
Kilian and Wigderson. In addition, this paper shows that the Random
Oracle Hypothesis is sensitive to small changes in the definition.
A class IPP, which is similar to IP, is defined. Surprisingly, the
IPP = PSPACE result holds for all oracle worlds.
Last Modified:
22 Jul 2024 11:27:55 EDT
by
Richard Chang