The random oracle hypothesis is false

DOI10.1016/S0022-0000(05)80084-4MaRDI QIDQ1333397zbMATH OpenOpenAlexDBLPWikidataFDO

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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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

• Are there interactive protocols for co-NP languages?
• Computational Complexity of Probabilistic Turing Machines
• Does co-NP have short interactive proofs ?
• scientific article; zbMATH DE number 4033067 (Why is no real title available?)
• scientific article; zbMATH DE number 4106274 (Why is no real title available?)
• 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 isomorphism conjecture fails relative to a random oracle
• The Knowledge Complexity of Interactive Proof Systems
• The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy Collapses
• The random oracle hypothesis is false

Cited in

(20)

• The generic oracle hypothesis is false
• Randomness in interactive proofs
• The random oracle hypothesis is false
• Interactive and probabilistic proof-checking
• Relativized worlds with an infinite hierarchy
• On the relationship between statistical zero-knowledge and statistical randomized encodings
• Hausdorff dimension and oracle constructions
• On the relationship between statistical zero-knowledge and statistical randomized encodings
• On the random oracle hypothesis
• scientific article; zbMATH DE number 58312 (Why is no real title available?)
• Towards the Actual Relationship Between NP and Exponential Time
• A hierarchy theorem for interactive proofs of proximity
• Strong self-reducibility precludes strong immunity
• On the power of statistical zero knowledge
• Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
• Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness
• Complexity barriers as independence
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
• Lower bounds for matroid optimization problems with a linear constraint
• Relativized succinct arguments in the ROM do not exist

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)