Hirahara, Shuichi
Identifying an Honest EXP^NP Oracle Among Many
Abstract
We provide a general framework to remove short advice by formulating the following computational task for a function f: given two oracles at least one of which is honest (i.e. correctly computes f on all inputs) as well as an input, the task is to compute f on the input with the help of the oracles by a probabilistic polynomialtime machine, which we shall call a selector. We characterize the languages for which short advice can be removed by the notion of selector: a paddable language has a selector if and only if short advice of a probabilistic machine that accepts the language can be removed under any relativized world.
Previously, instance checkers have served as a useful tool to remove short advice of probabilistic computation. We indicate that existence of instance checkers is a property stronger than that of removing short advice: although no instance checker for EXP^NPcomplete languages exists unless EXP^NP = NEXP, we prove that there exists a selector for any EXP^NPcomplete language, by building on the proof of MIP = NEXP by Babai, Fortnow, and Lund (1991).
BibTeX  Entry
@InProceedings{hirahara:LIPIcs:2015:5071,
author = {Shuichi Hirahara},
title = {{Identifying an Honest EXP^NP Oracle Among Many}},
booktitle = {30th Conference on Computational Complexity (CCC 2015)},
pages = {244263},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897811},
ISSN = {18688969},
year = {2015},
volume = {33},
editor = {David Zuckerman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5071},
URN = {urn:nbn:de:0030drops50718},
doi = {10.4230/LIPIcs.CCC.2015.244},
annote = {Keywords: nonuniform complexity, short advice, instance checker, interactive proof systems, probabilistic checkable proofs}
}
2015
Keywords: 

nonuniform complexity, short advice, instance checker, interactive proof systems, probabilistic checkable proofs 
Seminar: 

30th Conference on Computational Complexity (CCC 2015)

Issue date: 

2015 
Date of publication: 

2015 