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.