A parallel repetition theorem

Research output: Contribution to journalArticlepeer-review

493 Scopus citations


We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc. 11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70-76].

Original languageEnglish (US)
Pages (from-to)763-803
Number of pages41
JournalSIAM Journal on Computing
Issue number3
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • General Mathematics


  • Direct product
  • Interactive proofs
  • Parallel repetition


Dive into the research topics of 'A parallel repetition theorem'. Together they form a unique fingerprint.

Cite this