Technion
 
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
 
 Homepage:<http://www.technion.ac.il/~yehuday/colloquium/colloq.html>
 
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
science.
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Amir Yehudayoff   <amir.yehudayoff@gmail.com>