ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-142 | 18th September 2010 18:49

A Strong Parallel Repetition Theorem for Projection Games on Expanders

RSS-Feed




TR10-142
Authors: Ran Raz, Ricky Rosen
Publication: 18th September 2010 18:49
Downloads: 707
Keywords: 


Abstract:

The parallel repetition theorem states that for any Two
Prover Game with value at most $1-\epsilon$ (for $\epsilon<1/2$),
the value of the game repeated $n$ times in parallel is at most
$(1-\epsilon^3)^{\Omega(n/s)}$, where $s$ is the length of the
answers of the two provers. For Projection
Games, the bound on the value of the game repeated $n$ times in
parallel was improved to $(1-\epsilon^2)^{\Omega(n)}$
and this bound was shown to be tight.

In this paper we study the case
where the underlying distribution, according to which the questions
for the two provers are
generated, is uniform over the edges of a (bipartite) expander graph.

We show that if $\lambda$ is the (normalized) spectral gap of the
underlying graph, the value of the repeated game is at most
$$(1-\epsilon^2)^{\Omega(c(\lambda) \cdot n/ s)},$$ where
$c(\lambda) = poly(\lambda)$; and if in addition the game is a
projection game, we obtain a bound of $$(1-\epsilon)^{\Omega(
c(\lambda) \cdot n)},$$ where $c(\lambda) = poly(\lambda)$, that
is, a strong parallel repetition theorem (when $\lambda$ is
constant).

This gives a strong parallel repetition theorem for a large class
of two prover games.



ISSN 1433-8092 | Imprint