All reports by Author Ran Raz:

__
TR23-018
| 1st March 2023
__

Qipeng Liu, Ran Raz, Wei Zhan#### Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory

__
TR22-043
| 2nd April 2022
__

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan#### Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs

__
TR22-039
| 14th March 2022
__

Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, Wei Zhan#### Parallel Repetition For All 3-Player Games Over Binary Alphabet

__
TR20-173
| 18th November 2020
__

Kunal Mittal, Ran Raz#### Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines

Revisions: 1

__
TR20-120
| 12th August 2020
__

Justin Holmgren, Ran Raz#### A Parallel Repetition Theorem for the GHZ Game

__
TR20-101
| 7th July 2020
__

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

Qipeng Liu, Ran Raz, Wei Zhan

In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm for parity learning on $n$ bits requires either $\Omega(n^2)$ bits of classical memory or an exponential number (in~$n$) of random samples. A line of recent works continued that research direction and showed that for ... more >>>

Uma Girish, Kunal Mittal, Ran Raz, Wei Zhan

We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there ... more >>>

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

We prove that for every 3-player (3-prover) game, with binary questions and answers and value less than $1$, the value of the $n$-fold parallel repetition of the game decays polynomially fast to $0$. That is, for every such game, there exists a constant $c>0$, such that the value of the ... more >>>

Kunal Mittal, Ran Raz

We prove that a sufficiently strong parallel repetition theorem for a special case of multiplayer (multiprover) games implies super-linear lower bounds for multi-tape Turing machines with advice. To the best of our knowledge, this is the first connection between parallel repetition and lower bounds for time complexity and the first ... more >>>

Justin Holmgren, Ran Raz

We prove that parallel repetition of the (3-player) GHZ game reduces the value of the game polynomially fast to 0. That is, the value of the GHZ game repeated in parallel $t$ times is at most $t^{-\Omega(1)}$. Previously, only a bound of $\approx \frac{1}{\alpha(t)}$, where $\alpha$ is the inverse Ackermann ... 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 >>>