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
![]() ![]() ![]() ![]() ![]() ![]() ![]()
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 Available as PostScript, PDF, DVI. |