Computing and Combinatorics

DOI10.1007/11533719MaRDI QIDQ5716951zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Venkatesan T. Chakaravarthy

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11533719

Mathematics Subject Classification ID

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

Recommendations

• On zero error algorithms having oracle access to one query
• Amplification with one \textsf{NP} oracle query
• Query complexity in errorless hardness amplification
• Query complexity in errorless hardness amplification
• scientific article; zbMATH DE number 4060725
• The Zero-Error Randomized Query Complexity of the Pointer Function
• A note on the density of oracle decreasing time-space complexity
• On the pseudo-deterministic query complexity of NP search problems
• On a certain nontraditional version of computations with oracles
• Complexity bounds for zero-test algorithms

Cited in

(8)

• Amplification with one \textsf{NP} oracle query
• A zero-one law for RP and derandomization of AM if NP is not small
• On zero error algorithms having oracle access to one query
• A \(\mathrm{ZPP}^{\mathrm{NP}[1]}\) lifting theorem
• Amplification with one NP oracle query
• A \(\mathrm{ZPP}^{\mathrm{NP[1]}}\) lifting theorem
• \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
• The 1-versus-2 queries problem revisited

This page was built for publication: Computing and Combinatorics

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