2026-07-21T19:38:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17128 2024-03-06T10:59:02Z ddc:004 open_access

Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs Girish, Uma Mittal, Kunal Raz, Ran Zhan, Wei Parallel repetition Multi-prover games Fourier analysis We prove that for every 3-player (3-prover) game G with value less than one, whose query distribution has the support S = {(1,0,0), (0,1,0), (0,0,1)} of Hamming weight one vectors, the value of the n-fold parallel repetition G^{⊗n} decays polynomially fast to zero; that is, there is a constant c = c(G) > 0 such that the value of the game 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 G over binary questions and arbitrary answer lengths, with value less than 1, there is a constant c = c(G) > 0 such that the value of the game 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Uma Girish and Kunal Mittal and Ran Raz and Wei Zhan 2022 Is Part Of LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2022.6 urn:nbn:de:0030-drops-171286 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode