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

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)

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

Cites work

• scientific article; zbMATH DE number 4033067 (Why is no real title available?)
• scientific article; zbMATH DE number 4106274 (Why is no real title available?)
• Are there interactive protocols for co-NP languages?
• Computational Complexity of Probabilistic Turing Machines
• Does co-NP have short interactive proofs ?
• Non-deterministic exponential time has two-prover interactive protocols
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge 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
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Structural complexity theory: Recent surprises
• The Boolean Hierarchy I: Structural Properties
• The Boolean Hierarchy II: Applications
• The Knowledge Complexity of Interactive Proof Systems
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The isomorphism conjecture fails relative to a random oracle
• The random oracle hypothesis is false

Cited in

(18)

• Randomness in interactive proofs
• Interactive and probabilistic proof-checking
• The random oracle hypothesis is false
• On the power of statistical zero knowledge
• On the relationship between statistical zero-knowledge and statistical randomized encodings
• On the relationship between statistical zero-knowledge and statistical randomized encodings
• Complexity barriers as independence
• A hierarchy theorem for interactive proofs of proximity
• 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
• 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
• Title not available (Why is no real title available?)
• 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)