Israel CS THEORY DAY

Open University of Israel

Division of Computer Science

Date: 17.3.08

Speaker: Ran Raz

Title: A Counterexample to Strong Parallel Repetition

Abstract:

I will give a short introduction to the problem of parallel repetition of two-prover games and its applications to theoretical computer science, mathematics and physics, and will describe a recent counterexample to strong parallel repetition.

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 $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). Several researchers asked whether this bound could be improved to $(1- \epsilon)^{\Omega(n/s)}$; this question is usually referred to as the strong parallel repetition problem. A positive answer would have had important applications.

We show that the answer for this question is negative. More precisely, we consider the odd cycle game of size $m$; a two-prover game with value $1-1/2m$. We show that the value of the odd cycle game repeated in parallel $n$ times is at least $1- (1/m) \cdot O(\sqrt{n})$. This implies that for large enough $n$ (say, $n \geq \Omega(m^2)$), the value of the odd cycle game repeated in parallel $n$ times is at least $(1- 1/4m^2)^{O(n)}$.