Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-053 | 17th June 2004 00:00

Polylogarithmic Round Arthur-Merlin Games and Random-Self-Reducibility

RSS-Feed




TR04-053
Authors: A. Pavan, N. V. Vinodchandran
Publication: 22nd June 2004 18:17
Downloads: 3201
Keywords: 


Abstract:

We consider Arthur-Merlin proof systems where (a) Arthur is a probabilistic quasi-polynomial time Turing machine
and (AMQ)(b) Arthur is a probabilistic exponential time Turing machine (AME). We prove two new results related to these classes.



ISSN 1433-8092 | Imprint