Follow
Shalev Ben-David
Shalev Ben-David
Assistant Professor, University of Waterloo
Verified email at uwaterloo.ca - Homepage
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
852010
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
782016
Data stability in clustering: A closer look
S Ben-David, L Reyzin
Theoretical Computer Science 558, 51-61, 2014
352014
Quantum tokens for digital signatures
S Ben-David, O Sattath
arXiv preprint arXiv:1609.09047, 2016
292016
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
272016
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
23*2021
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
232016
Randomized Query Complexity of Sabotaged and Composed Functions
BD Shalev, R Kothari
43rd International Colloquium on Automata, Languages, and Programming (ICALP …, 2016
23*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
112020
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
112018
Sculpting quantum speedups
S Aaronson, S Ben-David
arXiv preprint arXiv:1512.04016, 2015
112015
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
82020
A new minimax theorem for randomized algorithms
S Ben-David, E Blais
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
82020
A super-Grover separation between randomized and quantum query complexities
S Ben-David
arXiv preprint arXiv:1506.08106, 2015
72015
Learning a classifier when the labeling is known
S Ben-David, S Ben-David
International Conference on Algorithmic Learning Theory, 440-451, 2011
62011
Unambiguous DNFs and Alon-Saks-Seymour
K Balodis, S Ben-David, M Göös, S Jain, R Kothari
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS …, 2022
5*2022
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
Scale-sensitive dimensions, uniform convergence
N Alon, S Ben-David, N Cesa-Bianchi, D Haussler
and learnability. Technical Report 143-95, DSI, University of Milan, Italy …, 0
5
On Query-to-Communication Lifting for Adversary Bounds
A Anshu, S Ben-David, S Kundu
arXiv preprint arXiv:2012.03415, 2020
42020
The structure of promises in quantum speedups
S Ben-David
arXiv preprint arXiv:1409.3323, 2014
42014
The system can't perform the operation now. Try again later.
Articles 1–20