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)

Full work available at URL https://doi.org/10.1016/S0019-9958(83)80023-0

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

(22)

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

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)