__Israel CS THEORY DAY__

Open University of

Division of Computer Science

__Date__**: 17.3.08**

__Speaker__**: Ran Raz**

__Title__**: A Counterexample to Strong Parallel Repetition
**

**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)}$.**