Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOMIZED COMPLEXITY CLASSES:
Reports tagged with randomized complexity classes:
TR99-033 | 19th August 1999
Vikraman Arvind, J. Köbler

Graph Isomorphism is Low for ZPP$^{\mbox{\rm NP}}$ and other Lowness results.

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 >>>




ISSN 1433-8092 | Imprint