BARC talk by Kunal Mittal

Thursday, November 28, 2024, Kunal Mittal, PhD student at Princeton University, USA, will give a talk on "Polynomial Bounds on Parallel Repetition For All 3-Player Games with Binary Inputs".

Abstract:

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

Kunal will talk about some progress on this problem, where they 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, they prove two additional parallel repetition theorems that may be of independent interest. They prove polynomial bounds for a large class of games, which they 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. They 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.

Bio:
Kunal Mittal is a PhD student in the Computer Science Theory Group at Princeton University, advised by Prof. Ran Raz. He obtained his undergraduate degree from IIT Bombay, India. His research interest is in complexity theory, and its connections to information theory, analysis of boolean functions, and combinatorics.

Host:
Srikanth Srinivasan