Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR08-013 | 16th January 2008 00:00

Parallel Repetition in Projection Games and a Concentration Bound

TR08-013
Authors: Anup Rao
Publication: 28th February 2008 09:39
Keywords:

Abstract:

In a two player game, a referee asks two cooperating players (who are
not allowed to communicate) questions sampled from some distribution
and decides whether they win or not based on some predicate of the
questions and their answers. The parallel repetition of the game is
the game in which the referee samples n independent pairs of
questions and sends corresponding questions to the players
simultaneously. If the players cannot win the original game with
probability better than (1-e), what's the best they can do in the
repeated game?

We improve earlier results of Raz and Holenstein, which showed
that the players cannot win all copies in the repeated game with
probability better than (1-e^3)^{\Omega(n/c)} (here c is the
length of the answers in the game), in the following ways:

We prove the bound (1-\e^2)^{Omega(n)} as long as n =
Omega(log(1/e)/e^2) and the game is a ``projection game'', the
type of game most commonly used in hardness of approximation
results. Our bound is independent of the answer length and has a
better dependence on e. By the recent work of Raz,
this bound is essentially tight (we might still hope to get rid of the
restriction on n). A consequence of this bound is that the Unique Games Conjecture of Khot is equivalent to:

[Unique Games Conjecture] For every delta,e >
0, there exists an alphabet size M(e) such that it is NP-hard to
distinguish a Unique Game with alphabet size M for which a 1-e^2
fraction of the constraints can be satisfied from one in which a
1-e^{1-delta} fraction of the constraints can be satisfied.

We prove a concentration bound for parallel repetition (of
general games) showing that for any constant 0<delta <e, the
probability that the players win a (1-e+delta) fraction of the
games in the parallel repetition is at most
exp(-Omega(delta^4 n/c)). An application of this is
in testing Bell Inequalities. Our result implies that the parallel
repetition of the CHSH game can be used to get an experiment that
has a very large classical versus quantum gap.

ISSN 1433-8092 | Imprint