Follow
Shalev Ben-David
Shalev Ben-David
Associate Professor, University of Waterloo
Verified email at uwaterloo.ca - Homepage
Title
Cited by
Cited by
Year
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
902016
Supporting ranking queries on uncertain and incomplete data
MA Soliman, IF Ilyas, S Ben-David
The VLDB Journal 19, 477-501, 2010
882010
Quantum tokens for digital signatures
S Ben-David, O Sattath
Quantum 7, 901, 2023
532023
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
53*2021
Data stability in clustering: A closer look
S Ben-David, L Reyzin
Theoretical Computer Science 558, 51-61, 2014
522014
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
302016
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
292020
Randomized query complexity of sabotaged and composed functions
S Ben-David, R Kothari
arXiv preprint arXiv:1605.09071, 2016
272016
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
252016
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
192018
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
162020
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
13*2023
Sculpting quantum speedups
S Aaronson, S Ben-David
arXiv preprint arXiv:1512.04016, 2015
132015
A new minimax theorem for randomized algorithms
S Ben-David, E Blais
Journal of the ACM 70 (6), 1-58, 2023
122023
On Query-to-Communication Lifting for Adversary Bounds
A Anshu, S Ben-David, S Kundu
arXiv preprint arXiv:2012.03415, 2020
102020
Learning a classifier when the labeling is known
S Ben-David, S Ben-David
International Conference on Algorithmic Learning Theory, 440-451, 2011
82011
A super-Grover separation between randomized and quantum query complexities
S Ben-David
arXiv preprint arXiv:1506.08106, 2015
72015
The structure of promises in quantum speedups
S Ben-David
arXiv preprint arXiv:1409.3323, 2014
72014
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
62016
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
42020
The system can't perform the operation now. Try again later.
Articles 1–20