All reports by Author Kunal Mittal:

__
TR22-043
| 2nd April 2022
__

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan#### Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

__
TR22-039
| 14th March 2022
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### Parallel Repetition For All 3-Player Games Over Binary Alphabet

__
TR21-101
| 13th July 2021
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof

Revisions: 1

__
TR20-173
| 18th November 2020
__

Kunal Mittal, Ran Raz#### Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Revisions: 1

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $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 ... more >>>

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

We give a new proof of the fact that the parallel repetition of the (3-player) GHZ game reduces the value of the game to zero polynomially quickly. That is, we show that the value of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

Kunal Mittal, Ran Raz

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>