Members’ Seminar

I will give an introduction to the problem of parallel repetition of two-prover games and its applications and related results in theoretical computer science (the PCP theorem, hardness of approximation), mathematics (the geometry of foams, tiling the space R^n) and, if time allows, 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 theoretical computer science, mathematics, and, if time allows, physics.