Derandomizing Arthur-Merlin Games using Hitting Sets

Peter Bro Miltersen
Vinodchandran N. Variyam

December 1999


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

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.