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 boolean AND coNE requires nondeterministic circuits of size 2(epsilon n). This improves results of Arvind and Kobler and of Klivans and van Melkebeek who proved the same conclusion, but under stronger hardness assumptions. The previous results on derandomizing A M 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 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.
derandomization graph nonisomorphism interactive proof systems complexity classes