The random oracle hypothesis is false

DOI10.1016/S0022-0000(05)80084-4zbMATH Open0813.68100DBLPjournals/jcss/ChangCGHHRR94OpenAlexW2016506875WikidataQ56959135 ScholiaQ56959135MaRDI QIDQ1333397FDOQ1333397

Authors: Richard Chang, Benny Chor, Oded Goldreich, J. Hartmanis, Desh Ranjan, Pankaj Rohatgi, Johan Hastad 

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

Recommendations

• On the random oracle hypothesis
• The generic oracle hypothesis is false
• The isomorphism conjecture fails relative to a random oracle
• Limits on the usefulness of random oracles
• Limits on the Usefulness of Random Oracles
• Random oracles and non-uniformity
• Bad oracles in higher computability and randomness
• Uniform van Lambalgen's theorem fails for computable randomness

zbMATH Keywords

complexity classesrandom oracle hypothesis

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (18)

• Randomness in interactive proofs
• Interactive and probabilistic proof-checking
• The random oracle hypothesis is false
• On the relationship between statistical zero-knowledge and statistical randomized encodings
• Complexity barriers as independence
• On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings
• Towards the Actual Relationship Between NP and Exponential Time
• On the random oracle hypothesis
• Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
• Relativized worlds with an infinite hierarchy
• On the Power of Statistical Zero Knowledge
• Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness
• Hausdorff dimension and oracle constructions
• Strong self-reducibility precludes strong immunity
• The generic oracle hypothesis is false
• A Hierarchy Theorem for Interactive Proofs of Proximity
• Title not available (Why is that?)
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE

This page was built for publication: The random oracle hypothesis is false

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1333397)