research
∙
07/20/2023
Quantum Logspace Computations are Verifiable
In this note, we observe that quantum logspace computations are verifiab...
share
research
∙
07/18/2023
On the works of Avi Wigderson
This is an overview of some of the works of Avi Wigderson, 2021 Abel pri...
research
∙
03/29/2023
Certified Hardness vs. Randomness for Log-Space
Let ℒ be a language that can be decided in linear space and let ϵ >0 be ...
research
∙
03/01/2023
Memory-Sample Lower Bounds for Learning with Classical-Quantum Hybrid Memory
In a work by Raz (J. ACM and FOCS 16), it was proved that any algorithm ...
research
∙
04/02/2022
Polynomial Bounds On Parallel Repetition For All 3-Player Games With Binary Inputs
We prove that for every 3-player (3-prover) game 𝒢 with value less than ...
research
∙
02/14/2022
Parallel Repetition For All 3-Player Games Over Binary Alphabet
We prove that for every 3-player game with binary questions and answers ...
research
∙
07/13/2021
Parallel Repetition for the GHZ Game: A Simpler Proof
We give a new proof of the fact that the parallel repetition of the (3-p...
research
∙
07/05/2021
Memory-Sample Lower Bounds for Learning Parity with Noise
In this work, we show, for the well-studied problem of learning parity u...
research
∙
06/22/2021
Eliminating Intermediate Measurements using Pseudorandom Generators
We show that quantum algorithms of time T and space S≥log T with unitary...
research
∙
11/18/2020
Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing Machines
We prove that a sufficiently strong parallel repetition theorem for a sp...
research
∙
09/02/2020
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
We prove that any two-pass graph streaming algorithm for the s-t reachab...
research
∙
08/12/2020
A Parallel Repetition Theorem for the GHZ Game
We prove that parallel repetition of the (3-player) GHZ game reduces the...
research
∙
07/07/2020
Lower Bounds for XOR of Forrelations
The Forrelation problem, introduced by Aaronson [A10] and Aaronson and A...
research
∙
06/08/2020
Quantum Logspace Algorithm for Powering Matrices with Bounded Norm
We give a quantum logspace algorithm for powering contraction matrices, ...
research
∙
02/17/2020
Time-Space Tradeoffs for Distinguishing Distributions and Applications to Security of Goldreich's PRG
In this work, we establish lower-bounds against memory bounded algorithm...
research
∙
11/06/2019
Quantum versus Randomized Communication Complexity, with Efficient Players
We study a new type of separation between quantum and classical communic...
research
∙
08/08/2017