Derandomizing Arthur-Merlin Games using Hitting Sets

Abstract

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.