Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

Abstract

We prove that for every 3-player (3-prover) game $\mathcal{G}$ with value less than one, whose query distribution has the support $\mathcal{S}=\{(1,0,0),(0,1,0),(0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition ${\mathcal{G}}^{\otimes n}$ decays polynomially fast to zero; that is, there is a constant $c=c(\mathcal{G})>0$ such that the value of the game ${\mathcal{G}}^{\otimes n}$ is at most $n^{-c}$. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For $\text{every}$ 3-player game $\mathcal{G}$ over $\text{binary questions}$ and $\text{arbitrary answer lengths}$, with value less than 1, there is a constant $c=c(\mathcal{G})>0$ such that the value of the game ${\mathcal{G}}^{\otimes n}$ is at most $n^{-c}$. Our proof technique is new and requires many new ideas. For example, we make use of the Level-$k$ inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.