An Efficient
Parallel Repetition Theorem for Arthur-Merlin Games
Muthu Venkitasubramaniam
Cornell University
Abstract:
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.