4 papers · 1 filter
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
Uma Girish, Kunal Mittal, Ran Raz +1
We prove that for every 3-player (3-prover) game with value less than one, whose query distribution has the support of ham…
Parallel Repetition For All 3-Player Games Over Binary Alphabet
Uma Girish, Justin Holmgren, Kunal Mittal +2
We prove that for every 3-player game with binary questions and answers and value , the value of the -fold parallel repetition of the game decays polynomially fast to 0. Tha…
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…
Lower Bounds for XOR of Forrelations
Uma Girish, Ran Raz, Wei Zhan
The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variant…