On the random oracle hypothesis

DOI10.1016/S0019-9958(83)80023-0zbMATH Open0549.68038MaRDI QIDQ3341897FDOQ3341897

Authors: Stuart A. Kurtz 

Publication date: 1983

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

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

zbMATH Keywords

counterexamplesrandom oracle hypothesis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (21)

• 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
• Title not available (Why is that?)
• 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
• On the cutting edge of relativization: The resource bounded injury method
• Circuit size relative to pseudorandom oracles
• 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
• On the Power of Threshold Measurements as Oracles

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)