All reports by Author Wei Zhan:

__
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

__
TR20-101
| 7th July 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Lower Bounds for XOR of Forrelations

__
TR20-087
| 8th June 2020
__

Uma Girish, Ran Raz, Wei Zhan#### Quantum Logspace Algorithm for Powering Matrices with Bounded Norm

Revisions: 2

__
TR19-162
| 15th November 2019
__

Ran Raz, Wei Zhan#### The Random-Query Model and the Memory-Bounded Coupon Collector

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan

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 >>>

Uma Girish, Ran Raz, Wei Zhan

The Forrelation problem, first introduced by Aaronson [AA10] and Aaronson and Ambainis [AA15], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [AA15]; the first separation between ... more >>>

Uma Girish, Ran Raz, Wei Zhan

We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq poly(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive ... more >>>

Ran Raz, Wei Zhan

We study a new model of space-bounded computation, the {\it random-query} model. The model is based on a branching-program over input variables $x_1,\ldots,x_n$. In each time step, the branching program gets as an input a random index $i \in \{1,\ldots,n\}$, together with the input variable $x_i$ (rather than querying an ... more >>>