2022/04/02 by Uma Girish, Kunal Mittal, Girish, Uma +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2204.00858
openalex publication_date 2022/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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⊗ 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⊗ 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 every 3-player game \mathcal G over binary questions and 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⊗ 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.