research
∙
09/04/2022
The Approximate Degree of DNF and CNF Formulas
The approximate degree of a Boolean function f{0,1}^n→{0,1} is the minim...
share
research
∙
08/24/2020
An Optimal Separation of Randomized and Quantum Query Complexity
We prove that for every decision tree, the absolute values of the Fourie...
research
∙
06/26/2020
Quantum Communication Complexity of Distribution Testing
The classical communication complexity of testing closeness of discrete ...
research
∙
09/16/2019
Vanishing-Error Approximate Degree and QMA Complexity
The ϵ-approximate degree of a function f X →{0, 1} is the least degree o...
research
∙
02/05/2019
The Hardest Halfspace
We study the approximation of halfspaces h:{0,1}^n→{0,1} in the infinity...
research
∙
01/04/2019
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0
The threshold degree of a Boolean function f{0,1}^n→{0,1} is the minimum...
research
∙
01/14/2018
Algorithmic Polynomials
The approximate degree of a Boolean function f(x_1,x_2,...,x_n) is the m...
research
∙
11/29/2017
