3 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
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…
cs.DS2016
Almost All Even Yao-Yao Graphs Are Spanners
Jian Li, Wei Zhan
It is an open problem whether Yao-Yao graphs (also known as sparse-Yao graphs) are all spanners when the integer parameter is large enough. In this paper we sho…