63 citations · 124 across the 20 of their papers we have counts for
6 papers · 1 filter
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
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 machin…
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
Sepehr Assadi, Ran Raz
We prove that any two-pass graph streaming algorithm for the - reachability problem in -vertex directed graphs requires near-quadratic space of bits. As a cor…
A Parallel Repetition Theorem for the GHZ Game
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 times…
Lower Bounds for XOR of Forrelations
Uma Girish, Ran Raz, Wei Zhan
The Forrelation problem, introduced by Aaronson [A10] and Aaronson and Ambainis [AA15], is a well studied problem in the context of separating quantum and classical models. Variant…
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
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 cont…
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
Sumegha Garg, Pravesh K. Kothari, Ran Raz
In this work, we establish lower-bounds against memory bounded algorithms for distinguishing between natural pairs of related distributions from samples that arrive in a streaming…