research
∙
08/26/2022
Randomised Composition and Small-Bias Minimax
We prove two results about randomised query complexity R(f). First, we i...
share
research
∙
02/16/2021
Unambiguous DNFs and Alon-Saks-Seymour
We exhibit an unambiguous k-DNF formula that requires CNF width Ω̃(k^2),...
research
∙
12/07/2020
On Query-to-Communication Lifting for Adversary Bounds
We investigate query-to-communication lifting theorems for models relate...
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
∙
06/23/2020
Symmetries, graph properties, and quantum speedups
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symm...
research
∙
06/19/2020
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Suppose we have randomized decision trees for an outer function f and an...
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
∙
02/25/2020
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
We prove two new results about the randomized query complexity of compos...
research
∙
02/25/2020
A New Minimax Theorem for Randomized Algorithms
The celebrated minimax principle of Yao (1977) says that for any Boolean...
research
∙
01/27/2020
How symmetric is too symmetric for large quantum speedups?
Suppose a Boolean function f is symmetric under a group action G acting ...
research
∙
02/10/2019
Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge
We define a new query measure we call quantum distinguishing complexity,...
research
∙
07/17/2018