An Analytical Approach to Parallel Repetition via CSP Inverse Theorems

Let G be a k-player game with value <1, whose query distribution is such that no marginal on k-1 players admits a non-trivial Abelian embedding. We show that for every n>=N, the value of the n-fold parallel repetition of G is val(G^n) <= 1/(log log ... log n), where the number of logarithms is C, and N=N(G) and 1 <= C <= k^(O(k)) are constants. As a consequence, we obtain a parallel repetition theorem for all 3-player games whose query distribution is pairwise-connected. Prior to our work, only inverse Ackermann decay bounds were known for such games. As additional special cases, we obtain a unified proof for all known parallel repetition theorems, albeit with weaker bounds: (1) A new analytic proof of parallel repetition for all 2-player games. (2) A new proof of parallel repetition for all k-player playerwise connected games. (3) Parallel repetition for all 3-player games (in particular 3-XOR games) whose query distribution has no non-trivial Abelian embedding into (Z, +). (4) Parallel repetition for all 3-player games with binary inputs.