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.


dimacs-www@dimacs.rutgers.edu
Document last modified on September 25, 1995