2 citations · 3 across the 10 of their papers we have counts for
6 papers · 1 filter
Fourier Growth of Communication Protocols for XOR Functions
Uma Girish, Makrand Sinha, Avishay Tal +1
The level- -Fourier weight of a Boolean function refers to the sum of absolute values of its level- Fourier coefficients. Fourier growth refers to the growth of these…
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…
Fourier Growth of Parity Decision Trees
Uma Girish, Avishay Tal, Kewen Wu
We prove that for every parity decision tree of depth on variables, the sum of absolute values of Fourier coefficients at level is at most $d^{\ell/2} \cdot O(\ell \…
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…