SPEAKER: Ricky Rosen TITLE: A Strong Parallel Repetition Theorem for Projection Games on Expanders Authors: Ran Raz and Ricky Rosen ABSTRACT: 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-\eps3)^{\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-\eps2)^{\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-\eps2)^{\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. LINKS: http://www.cs.tau.ac.il/~rosenric/papers/EPR.RR%20.pdf