Open AccessDerandomizing Arthur-Merlin Games using Hitting Sets
Author(s) -
Peter Bro Miltersen,
Vinodchandran N. Variyam
Publication year - 1999
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v6i47.20117
Subject(s) - nondeterministic algorithm , combinatorics , mathematics , intersection (aeronautics) , discrete mathematics , cone (formal languages) , oracle , electronic circuit , arithmetic , physics , computer science , algorithm , quantum mechanics , software engineering , engineering , aerospace engineering
We prove that AM (and hence Graph Nonisomorphism) is in NP if for some epsilon > 0, some language in NE intersection coNE requires nondeterministic circuits of size 2^(epsilon n). This improves recent results of Arvind and K¨obler and of Klivans and Van Melkebeek who proved the same conclusion, but under stronger hardness assumptions, namely, either the existence of a language in NE intersection coNE which cannot be approximated by nondeterministic circuits of size less than 2^(epsilon n) or the existence of a language in NE intersection coNE which requires oracle circuits of size 2^(epsilon n) with oracle gates for SAT (satisfiability). The previous results on derandomizing AM were based on pseudorandom generators. In contrast, our approach is based on a strengthening of Andreev, Clementi and Rolim's hitting set approach to derandomization. As a spin-off, we show that this approach is strong enough to give an easy (if the existence of explicit dispersers can be assumed known) proof of the following implication: For some epsilon > 0, if there is a language in E which requires nondeterministic circuits of size 2^(epsilon n), then P=BPP. This differs from Impagliazzo and Wigderson's theorem "only" by replacing deterministic circuits with nondeterministic ones.