On the random oracle hypothesis

DOI10.1016/S0019-9958(83)80023-0MaRDI QIDQ3341897zbMATH OpenFDO

Authors Stuart A. Kurtz

Publication date 1983

Published in Information and Control (Search for Journal in Brave)

zbMATH Keywords

counterexamplesrandom oracle hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The random oracle hypothesis is false
• On random oracle separations
• Deterministic random oracles
• scientific article; zbMATH DE number 1775406
• A random oracle for all of us

Cited in

(21)

• On the Power of Threshold Measurements as Oracles
• The random oracle hypothesis is false
• Degrees of Dowd-type generic oracles
• Barriers for succinct arguments in the random oracle model
• Limits on the Usefulness of Random Oracles
• scientific article; zbMATH DE number 421685 (Why is no real title available?)
• Bounded truth table does not reduce the one-query tautologies to a random oracle
• Augmented random oracles
• Random Oracles and Auxiliary Input
• The random oracle model: a twenty-year retrospective
• Circuit size relative to pseudorandom oracles
• On the cutting edge of relativization: The resource bounded injury method
• Towards the Actual Relationship Between NP and Exponential Time
• On independent random oracles
• Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
• On random oracle separations
• Random Oracle Reducibility
• Strong self-reducibility precludes strong immunity
• The generic oracle hypothesis is false
• On bounded query machines
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE

This page was built for publication: On the random oracle hypothesis

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