__
TR08-018 | 28th February 2008 00:00
__

#### A Counterexample to Strong Parallel Repetition

TR08-018
Authors:

Ran Raz
Publication: 1st March 2008 22:36

Downloads: 1377

Keywords:

**Abstract:**
The parallel repetition theorem states that for any two-prover game,

with value $1- \epsilon$ (for, say, $\epsilon \leq 1/2$), the value of

the game repeated in parallel $n$ times is at most

$(1- \epsilon^c)^{\Omega(n/s)}$, where $s$ is the answers' length

(of the original game) and $c$ is a universal constant.

Several researchers asked wether this bound could be improved

to $(1- \epsilon)^{\Omega(n/s)}$; this question is usually referred to

as the strong parallel repetition problem.

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

Thus:

1) For parallel repetition of general games:

the bounds of $(1- \epsilon^c)^{\Omega(n/s)}$ given in~\cite{R,Hol} are

of the right form, up to determining the exact value of the constant

$c \geq 2$.

2) For parallel repetition of XOR games, unique games and projection games: the bounds of $(1- \epsilon^2)^{\Omega(n)}$ given in~\cite{FKO}

(for XOR games) and in~\cite{Rao} (for unique and projection games) are

tight.

3) For parallel repetition of the odd cycle game:

the bound of $1- (1/m) \cdot \tilde{\Omega}(\sqrt{n})$ given

in~\cite{FKO} is almost tight.

A major motivation for the recent interest in the strong parallel

repetition problem is that a strong parallel repetition theorem

would have implied that the unique game conjecture is equivalent

to the NP hardness of distinguishing between instances of Max-Cut

that are at least $1 - \epsilon^2$ satisfiable from instances

that are at most $1 - (2/\pi) \cdot \epsilon$ satisfiable.

Our results suggest that this cannot be proved just by improving

the known bounds on parallel repetition.