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

Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs (via Zoom)

Abstract:  Understanding the behavior of multi-player games under parallel repetition is an important problem in theoretical computer science. The parallel repetition conjecture by Feige and Lovasz claims that for every game with value less than 1, its parallel repetition value goes down exponentially fast in the number of repetition.  While the conjecture is known to be true for all 2-player games (Raz '98), and a restricted family called connected games (Dinur, Harsha, Venkat, and Yuen '17), for every other multi-player game only inverse-Ackerman bounds are known (Verbitsky '96).  I will talk about some recent progress on this problem, where we prove that for any 3-player game over binary inputs, the value of the parallel repetition decays at least polynomially fast. Specifically, I will present the proofs for the family of games where the 3 players receive inputs of Hamming weight 1, and among them, a particularly interesting game called Anti-Correlation Game for which we obtain an exponential bound. These proofs used completely new ideas compared to all previous results on parallel repetition.  This is based on joint works with Uma Girish, Kunal Mittal, Justin Holmgren and Ran Raz.

Bio:  Wei Zhan is a Ph.D student in the theory group of the Department of Computer Science at Princeton University, advised by Prof. Ran Raz. His research interest lies in complexity theory, quantum computation and boolean function analysis.