Amplification with one \textsf{NP} oracle query

DOI10.1007/s00037-021-00219-wOpenAlexW4210627452MaRDI QIDQ2125078

Yanyan Li

Publication date: 12 April 2022

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-021-00219-w

zbMATH Keywords

oracleamplificationNP

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• The 1-versus-2 queries problem revisited
• Bounded queries to SAT and the Boolean hierarchy
• The landscape of communication complexity classes
• Saving queries with randomness
• On zero error algorithms having oracle access to one query
• On Approximation Algorithms for # P
• A ZPP ^NP[1 Lifting Theorem]

This page was built for publication: Amplification with one \textsf{NP} oracle query