LIPIcs.ICALP.2019.96.pdf
- Filesize: 0.52 MB
- 13 pages
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
Cite AsGet BibTex
Thomas Watson. Amplification with One NP Oracle Query. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 96:1-96:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.96
https://doi.org/10.4230/LIPIcs.ICALP.2019.96
Abstract
We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our inclusions are tight for relativizing techniques.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational complexity and cryptography
Keywords
- Amplification
- NP
- oracle
- query
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
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.