Derandomizing Arthur-Merlin Games using Hitting Sets
Peter Bro Miltersen
December 1999 |

## Abstract:
We prove that
AM (and hence Graph Nonisomorphism) is
in NP if for some , some language in NE
coNE requires nondeterministic circuits of size
. 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
coNE which cannot be approximated by nondeterministic
circuits of size less than
or the existence of a language in
NE coNE which requires oracle circuits of
size
with oracle gates for SAT
(satisfiability).
The previous results on derandomizing
Available as |

Last modified: 2003-06-08 by webmaster.