Mathematics Colloquium
Speaker: Ran Raz (Weizmann Institute)
Title: Parallel repetition of two prover games: a survey
Time: Monday, March 26, 3:30 pm
Place: Amado 232
Abstract: I will give an introduction to the problem
of parallel repetition of two-prover games and its applications in
theoretical computer science (the PCP theorem, hardness of
approximation), mathematics (the geometry of foams, tiling the space
R^n) and physics (Bell inequalities, the EPR paradox) . 
In a two-prover (alternatively, two-player) game, a referee chooses
questions (x,y) according to a (publicly known) distribution, and
sends x to the first player and y to the second player. The first
player responds by a=a(x) and the second by b=b(y) (without
communicating with each other). The players jointly win if a
(publicly known) predicate V(x,y,a,b) holds. The value of the game is
the maximal probability of success that the players can achieve,
where the maximum is taken over all protocols a=a(x),b=b(y).
A parallel repetition of a two-prover game is a game where the
players try to win n copies of the original game simultaneously. More
precisely, the referee generates questions x=(x_1,...,x_n),
y=(y_1,...,y_n), where each pair (x_i,y_i) is chosen independently
according to the original distribution. The players respond by
a=(a_1,...,a_n) and b=(b_1,...,b_n). The players win if they win
simultaneously on all the coordinates, that is, if for every i,
V(x_i,y_i,a_i,b_i) holds.
The parallel repetition theorem states that for any two-prover game
with value smaller than 1, parallel repetition reduces the value of
the game in an exponential rate. Formally, for any two-prover game
with value 1-epsilon (for, say, epsilon < 1/2), the value of the game
repeated in parallel n times is at most (1- epsilon^3)^Omega(n/s),
where s is the answers' length (of the original game).
I will discuss applications of the parallel repetition theorem and
related results in mathematics, physics and theoretical computer
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <> 
Announcement from: Amir Yehudayoff   <>