37 citations · 47 across the 4 of their papers we have counts for
5 papers · 1 filter
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari +2
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function , : The degree of…
No quantum speedup over gradient descent for non-smooth convex optimization
Ankit Garg, Robin Kothari, Praneeth Netrapalli +1
We study the first-order convex optimization problem, where we have black-box access to a (not necessarily smooth) function and its (sub)gradient. O…
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev Ben-David, Mika Göös, Robin Kothari +1
Suppose we have randomized decision trees for an outer function and an inner function . The natural approach for obtaining a randomized decision tree for the composed functi…
Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari +1
Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function , the deterministic query complexity, , is at most quartic in the quantum que…
Quantum Coupon Collector
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs +3
We study how efficiently a -element set can be learned from a uniform superposition of its elements. One can think of $|S\rangle=\sum_{i\in S}|i\rang…