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