2 citations · 4 across the 3 of their papers we have counts for
11 papers
On Query-to-Communication Lifting for Adversary Bounds
Anurag Anshu, Shalev Ben-David, Srijita Kundu
We investigate query-to-communication lifting theorems for models related to the quantum adversary bounds. Our results are as follows: 1. We show that the classical adversary bound…
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…
Symmetries, graph properties, and quantum speedups
Shalev Ben-David, Andrew M. Childs, András Gilyén +3
Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: h…
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…
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Shalev Ben-David, Eric Blais
We prove two new results about the randomized query complexity of composed functions. First, we show that the randomized composition conjecture is false: there are families of part…