A Counterexample to Strong Parallel Repetition

by Ran Raz

Oded's comments

In contrast to prior authors that were discouraged by the observation that providing such a counter-example will yield a surprising result regarding some problem in geometry (i.e., "foams"), Ran just provides such a counter-example (which subsequently led to the analogous "foam" result reported in Spherical Cubes and Rounding in High Dimensions [by Guy Kindler, Anup Rao, Ryan O'Donnell, and Avi Wigderson, 2008]). Ran considered the very same Odd-Cycle Game, which is a Unique Answer game and was considered before, and provides almost optimal strategies for this game. These strategies select an edge to cheat about at random, with probability distribution that decreases gradually (but exponentially (in a base adequately close to 1)) with the distance to the query.
The subsequent work Rounding Parallel Repetitions of Unique Games [by Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev and David Steurer] traces the source of the failure of the strong parallel repetition to a gap between the value of the game and the value of a SDP relaxation of the same game (which, as shown by Feige and Lovasz [1992], satisfies the strong parallel repetition).

The original 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. I will then describe a recent counterexample to the strong parallel repetition conjecture (a conjecture that would have had important applications).
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). The theorem has important applications in complexity theory, quantum computation, and geometry.
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.

Back to list of Oded's choices.