63 citations · 124 across the 20 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…
cs.LG2021★ 2 cited
Memory-Sample Lower Bounds for Learning Parity with Noise
Sumegha Garg, Pravesh K. Kothari, Pengda Liu +1
In this work, we show, for the well-studied problem of learning parity under noise, where a learner tries to learn from a stream of random linear…
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…