The random oracle hypothesis is false

DOI10.1016/S0022-0000(05)80084-4zbMath0813.68100OpenAlexW2016506875WikidataQ56959135 ScholiaQ56959135MaRDI QIDQ1333397

Benny Chor, Desh Ranjan, Oded Goldreich, Richard Chang, Pankaj Rohatgi, Juris Hartmanis, Johan T. Håstad

Publication date: 13 October 1994

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80084-4

zbMATH Keywords

complexity classesrandom oracle hypothesis

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The random oracle hypothesis is false, Hausdorff dimension and oracle constructions, A Hierarchy Theorem for Interactive Proofs of Proximity, Borel complexity and Ramsey largeness of sets of oracles separating complexity classes, On the Power of Statistical Zero Knowledge, Strong self-reducibility precludes strong immunity, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, On the relationship between statistical zero-knowledge and statistical randomized encodings, On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings, Interactive and probabilistic proof-checking, Towards the Actual Relationship Between NP and Exponential Time, Relativized worlds with an infinite hierarchy, Randomness in interactive proofs

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Does co-NP have short interactive proofs ?
• Are there interactive protocols for co-NP languages?
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The random oracle hypothesis is false
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The Knowledge Complexity of Interactive Proof Systems
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Computational Complexity of Probabilistic Turing Machines
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• The isomorphism conjecture fails relative to a random oracle
• Structural complexity theory: Recent surprises