Shalev Ben-David
Shalev Ben-David
Assistant Professor, University of Waterloo
Verified email at uwaterloo.ca
Title
Cited by
Cited by
Year
Supporting ranking queries on uncertain and incomplete data
MA Soliman, IF Ilyas, S Ben-David
The VLDB Journal 19 (4), 477-501, 2010
752010
Separations in query complexity using cheat sheets
S Aaronson, S Ben-David, R Kothari
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing …, 2016
682016
Data stability in clustering: A closer look
S Ben-David, L Reyzin
Theoretical Computer Science 558, 51-61, 2014
322014
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
252016
Separations in communication complexity using cheat sheets and information complexity
A Anshu, A Belovs, S Ben-David, M Göös, R Jain, R Kothari, T Lee, ...
2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS …, 2016
212016
Randomized Query Complexity of Sabotaged and Composed Functions
BD Shalev, R Kothari
43rd International Colloquium on Automata, Languages, and Programming (ICALP …, 2016
20*2016
Quantum tokens for digital signatures
S Ben-David, O Sattath
arXiv preprint arXiv:1609.09047, 2016
172016
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
S Aaronson, S Ben-David, R Kothari, S Rao, A Tal
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing …, 2021
11*2021
Classical lower bounds from quantum upper bounds
S Ben-David, A Bouland, A Garg, R Kothari
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS …, 2018
102018
Sculpting quantum speedups
S Aaronson, S Ben-David
arXiv preprint arXiv:1512.04016, 2015
102015
A tight composition theorem for the randomized query complexity of partial functions
S Ben-David, E Blais
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
62020
A super-Grover separation between randomized and quantum query complexities
S Ben-David
arXiv preprint arXiv:1506.08106, 2015
62015
Learning a classifier when the labeling is known
S Ben-David, S Ben-David
International Conference on Algorithmic Learning Theory, 440-451, 2011
62011
Symmetries, graph properties, and quantum speedups
S Ben-David, AM Childs, A Gilyén, W Kretschmer, S Podder, D Wang
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
52020
A new minimax theorem for randomized algorithms
S Ben-David, E Blais
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
52020
Separating quantum communication and approximate rank
A Anshu, S Ben-David, A Garg, R Jain, R Kothari, T Lee
arXiv preprint arXiv:1611.05754, 2016
52016
The structure of promises in quantum speedups
S Ben-David
arXiv preprint arXiv:1409.3323, 2014
32014
Unambiguous DNFs and Alon-Saks-Seymour
K Balodis, S Ben-David, M Göös, S Jain, R Kothari
arXiv preprint arXiv:2102.08348, 2021
2*2021
When Is Amplification Necessary for Composition in Randomized Query Complexity?
S Ben-David, M Göös, R Kothari, T Watson
arXiv preprint arXiv:2006.10957, 2020
22020
On Rota's Conjecture and nested separations in matroids
S Ben-David, J Geelen
Journal of Combinatorial Theory, Series B 119, 1-11, 2016
22016
The system can't perform the operation now. Try again later.
Articles 1–20