research
∙
08/06/2022
An Optimal "It Ain't Over Till It's Over" Theorem
We study the probability of Boolean functions with small max influence t...
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
∙
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
∙
09/18/2018