TY - GEN

T1 - Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs

AU - Girish, Uma

AU - Mittal, Kunal

AU - Raz, Ran

AU - Zhan, Wei

N1 - Funding Information:
Funding Uma Girish: Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award, by the National Science Foundation grants No. CCF-1714779, CCF-2007462 and by the IBM Phd Fellowship. Kunal Mittal: Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462. Ran Raz: Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462. Wei Zhan: Research supported by the Simons Collaboration on Algorithms and Geometry, by a Simons Investigator Award and by the National Science Foundation grants No. CCF-1714779, CCF-2007462.
Publisher Copyright:
© Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan.

PY - 2022/9/1

Y1 - 2022/9/1

N2 - 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 nfold 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.

AB - 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 nfold 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.

KW - Fourier analysis

KW - Multi-prover games

KW - Parallel repetition

UR - http://www.scopus.com/inward/record.url?scp=85139090065&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85139090065&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX/RANDOM.2022.6

DO - 10.4230/LIPIcs.APPROX/RANDOM.2022.6

M3 - Conference contribution

AN - SCOPUS:85139090065

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022

A2 - Chakrabarti, Amit

A2 - Swamy, Chaitanya

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022

Y2 - 19 September 2022 through 21 September 2022

ER -