An efficient parallel repetition theorem for Arthur-Merlin games. (English) Zbl 1232.68057

Pass, Katael; Venkitasubramaniam, Muthuramakrishnan

STOC’07. Proceedings of the 39th annual ACM symposium on theory of computing, San Diego, CA, USA, June 11–13, 2007. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-59593-631-8). 420-429 (2007).

For the entire collection see [Zbl 1146.68002].

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Keywords:

Arthur-Merlin games; interactive proof system; parallel-repetition theorem; reduction