An Efficient Parallel Repetition Theorem for Arthur-Merlin Games



Muthu Venkitasubramaniam

Cornell University

Monday  April 2, 2007
4:00 PM, 5130 Upson Hall



We show a parallel-repetition theorem for constant-round Arthur-Merlin Games using an efficient reduction. As a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coin proofs of knowledge. The former of these results resolves an open question posed by Bellare, Impagliazzo and Naor (FOCS '97).

Joint work with Rafael Pass.