Seguir
Shalev Ben-David
Shalev Ben-David
Associate Professor, University of Waterloo
Dirección de correo verificada de uwaterloo.ca - Página principal
Título
Citado por
Citado por
Año
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
912016
Supporting ranking queries on uncertain and incomplete data
MA Soliman, IF Ilyas, S Ben-David
The VLDB Journal 19, 477-501, 2010
892010
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
55*2021
Quantum tokens for digital signatures
S Ben-David, O Sattath
Quantum 7, 901, 2023
542023
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
282016
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
202018
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
172020
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
112020
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
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
42022
El sistema no puede realizar la operación en estos momentos. Inténtalo de nuevo más tarde.
Artículos 1–20