A Strong Parallel Repetition Theorem for Projection Games on Expanders
Speaker: Ricky Rosen , Weizmann Institute
Date: November 23 2010
Time: 4:15PM to 5:15PM
Location: 32-144
Host: Scott Aaronson, CSAIL, MIT
Contact: Be Blackburn , 3-6098, imbe@mit.edu
The parallel repetition theorem states that for any Two
Prover Game with value at most 1-\eps (for \eps<1/2),
the value of the game repeated n times in parallel is at most
(1-\eps^3)^{\Omega(n/s)}, where s is the length of the
answers of the two provers \cite{R,Hol}. For Projection
Games, the bound on the value of the game repeated n times in
parallel was improved to (1-\eps^2)^{\Omega(n)} \cite{Rao}
and this bound was shown to be tight \cite{R08}.
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-\eps^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-\eps)^{\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.
This is a joint work with Ran Raz.
See other events that are part of Theory Colloquium 2010/2011
See other events happening in November 2010
