The parallel repetition theorem states that for any Two Prover Game with value at most 1-€ (for €3)Ω(n/s), where s is the length of the answers of the two provers [24], [17]. For Projection Games, the bound on the value of the game repeated n times in parallel was improved to (1 - €2)Ω(n)[23] and this bound was shown to be tight [25]. 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 λ is the (normalized) spectral gap of the underlying graph, the value of the repeated game is at most (1 - €2)Ω(c(λ)·n/s), where c(λ) = poly(λ); and if in addition the game is a projection game, we obtain a bound of (1 - €)Ω(c(λ)·n), where c(λ) = poly(λ), that is, a strong parallel repetition theorem (when λ is constant). This gives a strong parallel repetition theorem for a large class of two prover games.

We present reductions from lattice problems in the l2 norm to the corresponding problems in other norms such as l1, l∞ (and in fact in any other lp norm where 1 ≤ p ≤ ∞). We consider lattice problems such as the Shortest Vector Problem, Shortest Independent Vector Problem, Closest Vector Problem and the Closest Vector Problem with Preprocessing. Most reductions are simple and follow from known constructions of embeddings of normed spaces.Among other things, our reductions imply that the Shortest Vector Problem in the l1 norm and the Closest Vector Problem with Preprocessing in the l∞ norm are hard to approximate to within any constant (and beyond). Previously, the former problem was known to be hard to approximate to within 2-ε, while no hardness result was known for the latter problem.