research
∙
07/26/2023
Fourier Growth of Communication Protocols for XOR Functions
The level-k ℓ_1-Fourier weight of a Boolean function refers to the sum o...
share
research
∙
07/20/2023
Quantum Logspace Computations are Verifiable
In this note, we observe that quantum logspace computations are verifiab...
research
∙
06/02/2023
Trade-offs between Entanglement and Communication
We study the advantages of quantum communication models over classical c...
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
∙
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
∙
03/22/2021
Fourier Growth of Parity Decision Trees
We prove that for every parity decision tree of depth d on n variables, ...
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
∙
11/06/2019