A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs
Rafael Pass, Muthuramakrishnan Venkitasubramaniam · ACM Transactions on Computation Theory · 2012
We show a parallel-repetition theorem for constant-round Arthur-Merlin Proofs, 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 first of these results resolves an open question posed by Bellare, Impagliazzo, and Naor (FOCS’97).