Vikraman Arvind, J. Köbler

We show the following new lowness results for the probabilistic

class ZPP$^{\mbox{\rm NP}}$.

1. The class AM$\cap$coAM is low for ZPP$^{\mbox{\rm NP}}$.

As a consequence it follows that Graph Isomorphism and several

group-theoretic problems known to be in AM$\cap$coAM are low for

ZPP$^{\mbox{\rm ...
more >>>