Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-058 | 5th April 2018 05:59

Amplification with One NP Oracle Query

RSS-Feed




TR18-058
Authors: Thomas Watson
Publication: 5th April 2018 12:01
Downloads: 160
Keywords: 


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.



ISSN 1433-8092 | Imprint