Next: Fault-tolerant Computations without Assumptions:
Up: The Technion Period (1986-94)
Previous: Randomness in Interactive Proofs
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
- JCSS, Vol. 49, No. 1 (1994), pp. 24-39.
Oded Goldreich
2003-07-30