ECCC-Report TR22-043https://eccc.weizmann.ac.il/report/2022/043Comments and Revisions published for TR22-043en-usSat, 02 Apr 2022 16:37:18 +0300
Paper TR22-043
| Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs |
Kunal Mittal,
Wei Zhan,
Uma Girish,
Ran Raz
https://eccc.weizmann.ac.il/report/2022/043We 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 $\textbf{every}$ 3-player game $\mathcal G$ over $\textit{binary questions}$ and $\textit{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.Sat, 02 Apr 2022 16:37:18 +0300https://eccc.weizmann.ac.il/report/2022/043