next up previous
Next: Fault-tolerant Computations without Assumptions: Up: The Technion Period (1986-94) Previous: Randomness in Interactive Proofs

The Random Oracle Hypothesis is False

It is shown that relative to a random oracle, coNP is not contained in IP. Combined with the (non-relativizing) containment of coNP in IP (proved by Lund, Fortnow, Karloff and Nisan) this yields a dramatic refutation of the Random Oracle Hypothesis.


Comments: Authored by R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad, D. Ranjan and P. Rohatgi. Appeared in



Oded Goldreich
2003-07-30