The global power of additional queries to random oracles

DOI10.1006/INCO.1995.1097MaRDI QIDQ1898477zbMATH OpenOpenAlexFDO

Authors Ronald V. Book, Jack H. Lutz, David M. jun. Martin

Publication date 17 September 1995

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://lib.dr.iastate.edu/cgi/viewcontent.cgi?article=1131&context=cs_techreports

zbMATH Keywords

algorithmically random languageRAND

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Publication:4942646
• scientific article; zbMATH DE number 512800
• The global power of additional queries to \(p\)-random oracles
• On complexity classes and algorithmically random languages (extended abstract)
• scientific article; zbMATH DE number 1670881

Cited in

(8)

• The global power of additional queries to \(p\)-random oracles
• On the power of two-local random reductions
• The power of adaptiveness and additional queries in random-self- reductions
• Some connections between bounded query classes and non-uniform complexity.
• scientific article; zbMATH DE number 1670881 (Why is no real title available?)
• scientific article; zbMATH DE number 1414309 (Why is no real title available?)
• 2-local random reductions to 3-valued functions
• scientific article; zbMATH DE number 177821 (Why is no real title available?)

This page was built for publication: The global power of additional queries to random oracles

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