All reports by Author Ran Raz:

__
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

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