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:

TR23-107 | 20th July 2023
Uma Girish, Ran Raz, Wei Zhan

Quantum Logspace Computations are Verifiable

In this note, we observe that quantum logspace computations are verifiable by classical logspace algorithms, with unconditional security. More precisely, every language in BQL has an information-theoretically secure) streaming proof with a quantum logspace prover and a classical logspace verifier. The prover provides a polynomial-length proof that is streamed to ... more >>>

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

Revisions: 1

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