2 papers
cs.CC2021
Parallel Repetition for the GHZ Game: A Simpler Proof
Uma Girish, Justin Holmgren, Kunal Mittal +2
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…
cs.CC2020
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
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 machin…