3 citations · 7 across the 12 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
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…
quant-ph2021
Eliminating Intermediate Measurements using Pseudorandom Generators
Uma Girish, Ran Raz
We show that quantum algorithms of time and space with unitary operations and intermediate measurements can be simulated by quantum algorithms of time $T \cdot \m…
cs.CC2021
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 \…