Computer Science/Discrete Mathematics Seminar I

Understanding the behavior of multi-player (multi-prover) games under parallel repetition is an important problem in theoretical computer science.

In a $k$-player game $G$, a referee chooses questions $(x^{1}, ..., x^{k})$ from a (publicly known) distribution $Q$, and for each $j$ in ${1, ..., k}$, sends the question $x_{j}$ to player $j$. Then, each player $j$, based on the question they received, gives back an answer $a^{j}$. Finally, the referee says whether the players win or lose based on the evaluation of a (publicly known) predicate $V(x^{1}, ..., x^{k}, a^{1}, ..., a^{k})$. The value of the game is defined to be the maximum winning probability for the players, where the maximum is over the possible strategies of the players.

In the n-fold parallel repetition $G^{n}$ of the above game, the players are given (independently sampled) questions for $n$ copies of the game and their goal is to win all copies. More formally, for each $i$ in ${1, ..., n}$, the referee samples $(x_{i^{1}}, ..., x_{i^{k}})$ independently from $Q$. For each $j$ in ${1, ..., k}$, player $j$ is given the questions $(x_{1^{j}}, ..., x_{n^{j}})$, based on which they answer $(a_{1^{j}}$, ..., $a_{n^{j}})$. The players are said to win if $V(x_{i^{1}}, ..., x_{i^{k}}$, $a_{i^{1}}$, ..., $a_{i^{k}})$ evaluates to true for each ${i}$.

While for every 2-player game G with value $<1$, the value of the game $G^{n}$ is known to decrease exponentially in n (Raz ’98), only inverse-Ackerman bounds are known for general k-player games (Verbitsky ’96).

I will talk about some recent progress on this problem, where we prove that for any 3-player game over binary inputs, with value $<1$, the value of the n-fold parallel repetition decays polynomially fast to 0. Along the way, we prove two additional parallel repetition theorems that may be of independent interest. We prove polynomial bounds for a large class of games, which we call Playerwise Connected Games, with any number of players and any input length. This class extends the class of Connected Games of Dinur, Harsha, Venkat, and Yuen ’17 for which exponential bounds are known. We also prove exponential bounds for a 3-player game that we call the Anti-Correlation Game, which was studied and motivated in several previous works. In particular, Holmgren and Yang ’19 gave it as an example for a 3-player game whose non-signaling value is smaller than 1 and yet does not decrease at all under parallel repetition, and thus our result implies an example for a 3-player game where the value of the parallel repetition of the game behaves completely differently for classical strategies versus non-signaling strategies.

This is based on joint works with Uma Girish, Justin Holmgren, Ran Raz, and Wei Zhan.