Shalev Ben-David
Shalev Ben-David
Associate Professor, University of Waterloo
Verified email at - Homepage
Cited by
Cited by
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
Supporting ranking queries on uncertain and incomplete data
MA Soliman, IF Ilyas, S Ben-David
The VLDB Journal 19, 477-501, 2010
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
Quantum tokens for digital signatures
S Ben-David, O Sattath
Quantum 7, 901, 2023
Data stability in clustering: A closer look
S Ben-David, L Reyzin
Theoretical Computer Science 558, 51-61, 2014
Randomized query complexity of sabotaged and composed functions
S Ben-David, R Kothari
arXiv preprint arXiv:1605.09071, 2016
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
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
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
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
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
Unambiguous DNFs and Alon–Saks–Seymour
K Balodis, S Ben-David, M Göös, S Jain, R Kothari
SIAM Journal on Computing, FOCS21-157-FOCS21-173, 2023
Sculpting quantum speedups
S Aaronson, S Ben-David
arXiv preprint arXiv:1512.04016, 2015
A new minimax theorem for randomized algorithms
S Ben-David, E Blais
Journal of the ACM 70 (6), 1-58, 2023
On Query-to-Communication Lifting for Adversary Bounds
A Anshu, S Ben-David, S Kundu
Proceedings of the 36th Computational Complexity Conference, 2021
Learning a classifier when the labeling is known
S Ben-David, S Ben-David
International Conference on Algorithmic Learning Theory, 440-451, 2011
A super-Grover separation between randomized and quantum query complexities
S Ben-David
arXiv preprint arXiv:1506.08106, 2015
The structure of promises in quantum speedups
S Ben-David
arXiv preprint arXiv:1409.3323, 2014
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
Randomised composition and small-bias minimax
S Ben-David, E Blais, M Göös, G Maystre
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS …, 2022
The system can't perform the operation now. Try again later.
Articles 1–20