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
∙
12/01/2022
Quantum Cryptography in Algorithmica
We construct a classical oracle relative to which 𝖯 = 𝖭𝖯 yet single-copy...
research
∙
06/01/2021
Junta Distance Approximation with Sub-Exponential Queries
Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two dif...
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
∙
12/03/2020
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for 𝐀𝐂^0
Håstad showed that any De Morgan formula (composed of AND, OR and NOT ga...
research
∙
10/23/2020
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
research
∙
05/06/2020
Rigid Matrices From Rectangular PCPs
We introduce a variant of PCPs, that we refer to as rectangular PCPs, wh...
research
∙
04/28/2020
Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
research
∙
12/29/2019
Towards Optimal Separations between Quantum and Randomized Query Complexities
The query model offers a concrete setting where quantum algorithms are p...
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
∙
06/20/2019
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search p...
research
∙
06/11/2018
Pseudorandom Generators for Width-3 Branching Programs
We construct pseudorandom generators of seed length Õ((n)·(1/ϵ)) that ϵ-...
research
∙
08/08/2017