Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ran Raz:

TR21-101 | 13th July 2021
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

A Parallel Repetition Theorem for the GHZ Game: A Simpler Proof

Revisions: 1

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 of the $n$-fold GHZ game is at most $n^{-\Omega(1)}$. This was first established by Holmgren and ... more >>>

TR21-087 | 22nd June 2021
Uma Girish, Ran Raz

Eliminating Intermediate Measurements using Pseudorandom Generators

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>

ISSN 1433-8092 | Imprint