Derandomizing Arthur-Merlin Games using Hitting Sets

We prove that AM (and hence Graph Nonisomorphism) is in NP if for some $\epsilon>0$ , some language in NE $\cap$ coNE requires nondeterministic circuits of size $2^{\epsilon n}$ . This improves recent results of Arvind and Köbler 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 $\cap$ coNE which cannot be approximated by nondeterministic circuits of size less than $2^{\epsilon n}$ or the existence of a language in NE $\cap$ 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

Abstract: