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

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022
EditorsAmit Chakrabarti, Chaitanya Swamy
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772495
DOIs
StatePublished - Sep 1 2022
Event25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022 - Virtual, Urbana-Champaign, United States
Duration: Sep 19 2022Sep 21 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume245
ISSN (Print)1868-8969

Conference

Conference25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022
Country/TerritoryUnited States
CityVirtual, Urbana-Champaign
Period9/19/229/21/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Fourier analysis
  • Multi-prover games
  • Parallel repetition

Fingerprint

Dive into the research topics of 'Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs'. Together they form a unique fingerprint.

Cite this