Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR99-033 | 19th August 1999 00:00

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


Authors: Vikraman Arvind, J. Köbler
Publication: 7th September 1999 22:09
Downloads: 1118


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 NP}}$.
2. The class IP[P$/$poly], consisting of sets that have interactive
proof systems with honest provers in P$/$poly
are also low for ZPP$^{\mbox{\rm NP}}$.

We consider lowness properties of nonuniform function classes:
NPMV$/$poly, NPSV$/$poly, NPMV$_t/$poly, and NPSV$_t/$poly.
Specifically, we show that:

3. Sets whose characteristic functions are in NPSV$/poly$ and that
have program checkers (in the sense of Blum and Kannan~\cite{BK})
are low for AM and ZPP$^{\mbox{\rm NP}}$.
4. Sets whose characteristic functions are in NPMV$_t/poly$ are low
for $\Sigma^p_2$.

ISSN 1433-8092 | Imprint