Document
Amplification with One NP Oracle Query
Author
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
PDF
LIPIcs.ICALP.2019.96.pdf
- Filesize: 0.52 MB
- 13 pages
References
- Richard Beigel. Bounded Queries to SAT and the Boolean Hierarchy. Theoretical Computer Science, 84(2):199-223, 1991. URL: http://dx.doi.org/10.1016/0304-3975(91)90160-4.
- Jin-Yi Cai and Venkatesan Chakaravarthy. On Zero Error Algorithms Having Oracle Access to One Query. Journal of Combinatorial Optimization, 11(2):189-202, 2006. URL: http://dx.doi.org/10.1007/s10878-006-7130-0.
- Richard Chang and Suresh Purini. Amplifying ZPP^SAT[1] and the Two Queries Problem. In Proceedings of the 23rd Conference on Computational Complexity (CCC), pages 41-52. IEEE, 2008. URL: http://dx.doi.org/10.1109/CCC.2008.32.
- Rahul Tripathi. The 1-Versus-2 Queries Problem Revisited. Theory of Computing Systems, 46(2):193-221, 2010. URL: http://dx.doi.org/10.1007/s00224-008-9126-x.
-
Nikolai Vereshchagin. Relativizability in Complexity Theory. In Provability, Complexity, Grammars, volume 192 of AMS Translations, Series 2, pages 87-172. American Mathematical Society, 1999.
- Thomas Watson. Amplification with One NP Oracle Query. Technical Report TR18-058, Electronic Colloquium on Computational Complexity (ECCC), 2018. URL: https://eccc.weizmann.ac.il/report/2018/058/.
- Thomas Watson. A ZPP^NP[1] Lifting Theorem. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 59:1-59:16. Schloss Dagstuhl, 2019. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2019.59.