DIMACS Theory of Computing Seminar

Title:

A Parallel Repetition Theorem

Speaker:

Ran Raz

Weizmann Institute

Place:

CoRE Building, Room 431

Busch Campus, Rutgers University

Time:

4:30 PM

Thursday, October 5, 1995

Abstract:

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