DIMACS Theory of Computing Seminar


A Parallel Repetition Theorem


Ran Raz
Weizmann Institute


CoRE Building, Room 431
Busch Campus, Rutgers University


4:30 PM
Thursday, October 5, 1995


We show that a parallel repetition of two-prover one-round proof systems MIP(2,1) reduces the probability of error at an exponential rate. This settles a standing open problem, sometimes called ``The Parallel Repetition Conjecture''. Previously, no constructive bound was known. The constant we have in the exponent is logarithmic in the total number of possible answers of the two provers. In the most frequently used cases, our constant is just a global constant.

In this talk I will give an introduction to the subject, without trying to describe any proof.

Document last modified on September 25, 1995