# CSAIL Event Calendar: Previous Series

 A Strong Parallel Repetition Theorem for Projection Games on ExpandersSpeaker: Ricky Rosen , Weizmann InstituteDate: November 23 2010 Time: 4:15PM to 5:15PM Location: 32-144Host: Scott Aaronson, CSAIL, MITContact: Be Blackburn , 3-6098, imbe@mit.eduThe 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/2011See other events happening in November 2010