
Unambiguous DNFs and AlonSaksSeymour
We exhibit an unambiguous kDNF formula that requires CNF width Ω̃(k^2),...
read it

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...
read it

No quantum speedup over gradient descent for nonsmooth convex optimization
We study the firstorder convex optimization problem, where we have blac...
read it

When Is Amplification Necessary for Composition in Randomized Query Complexity?
Suppose we have randomized decision trees for an outer function f and an...
read it

Quantum Implications of Huang's Sensitivity Theorem
Based on the recent breakthrough of Huang (2019), we show that for any t...
read it

Exponential separation between shallow quantum circuits and unbounded fanin shallow classical circuits
Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search p...
read it

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
This paper proves new limitations on the power of quantum computers to s...
read it

Quantum distinguishing complexity, zeroerror algorithms, and statistical zero knowledge
We define a new query measure we call quantum distinguishing complexity,...
read it

Quantum algorithms and approximating polynomials for composed functions with shared inputs
We give new quantum algorithms for evaluating composed functions whose i...
read it

Classical lower bounds from quantum upper bounds
We prove lower bounds on complexity measures, such as the approximate de...
read it

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
The approximate degree of a Boolean function f is the least degree of a ...
read it
Robin Kothari
is this you? claim profile