A Parallel Repetition Theorem for Constant-Round Arthur-Merlin Proofs
Abstract
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).
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2012
- Source ID
- 10.1145/2382559.2382561
Entities
People
- Muthuramakrishnan Venkitasubramaniam
- Rafael Pass
Organizations
- Air Force Office of Scientific Research
- Air Force Research Laboratory
- Bulgarian Science Fund
- Cornell University
- University of Rochester