TR99-033 Authors: Vikraman Arvind, J. Köbler

Publication: 7th September 1999 22:09

Downloads: 1118

Keywords:

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