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>