STOC2022
Parallel repetition for all 3-player games over binary alphabet
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan
6 citations
Abstract
We prove that for every 3-player (3-prover) game, with binary questions and answers and value <1, the value of the n-fold parallel repetition of the game decays polynomially fast to 0. That is, for every such game, there exists a constant c>0, such that the value of the n-fold parallel repetition of the game is at most n−c.