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