Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-043 | 2nd April 2022 16:13

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

RSS-Feed




TR22-043
Authors: Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan
Publication: 2nd April 2022 16:37
Downloads: 609
Keywords: 


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 \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.



ISSN 1433-8092 | Imprint