ContactPerson: aduri@cse.buffalo.edu
Remote host: cygnus.cse.buffalo.edu
Remote ident: aduri
### Begin Citation ### Do not delete this line ###
%R 2000-11
%U /u0/csgrad/aduri/tmp/paper.ps
%A Charles, D.
%A  Pavan, A.
%A  Sengupta, S.
%T On higher Arthur-Merlin classes
%D December 12, 2000
%I Department of Computer Science and Engineering, SUNY Buffalo
%X We study higher Arthur-Merlin 
classes defined via several natural probabilistic 
operators BP, R and coR. 
We investigate the complexity 
classes they define, and a number of 
interactions between these operators and the standard 
polynomial time hierarchy. 
%operators Sigma_k and Pi_k. 
We prove a hierarchy theorem for these higher 
Arthur-Merlin 
classes involving interleaving operators, and 
a  theorem giving non-trivial upper bounds 
to the intersection of 
the complementary classes in the hierarchy.