Obserwuj
Shalev Ben-David
Shalev Ben-David
Associate Professor, University of Waterloo
Zweryfikowany adres z uwaterloo.ca - Strona główna
Tytuł
Cytowane przez
Cytowane przez
Rok
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
1012016
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
72*2021
Quantum tokens for digital signatures
S Ben-David, O Sattath
Quantum 7, 901, 2023
702023
Data stability in clustering: A closer look
S Ben-David, L Reyzin
Theoretical Computer Science 558, 51-61, 2014
412014
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
362020
Randomized query complexity of sabotaged and composed functions
S Ben-David, R Kothari
arXiv preprint arXiv:1605.09071, 2016
352016
Low-sensitivity functions from unambiguous certificates
S Ben-David, P Hatami, A Tal
arXiv preprint arXiv:1605.07084, 2016
352016
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
272016
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
242020
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
232018
A new minimax theorem for randomized algorithms
S Ben-David, E Blais
Journal of the ACM 70 (6), 1-58, 2023
142023
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
14*2023
On Query-to-Communication Lifting for Adversary Bounds
A Anshu, S Ben-David, S Kundu
Proceedings of the 36th Computational Complexity Conference, 2021
142021
Sculpting quantum speedups
S Aaronson, S Ben-David
arXiv preprint arXiv:1512.04016, 2015
142015
Learning a classifier when the labeling is known
S Ben-David, S Ben-David
International Conference on Algorithmic Learning Theory, 440-451, 2011
82011
The structure of promises in quantum speedups
S Ben-David
Proceedings of the 11th Conference on the Theory of Quantum Computation …, 2016
72016
A super-Grover separation between randomized and quantum query complexities
S Ben-David
arXiv preprint arXiv:1506.08106, 2015
72015
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
62022
When is amplification necessary for composition in randomized query complexity?
S Ben-David, M Göös, R Kothari, T Watson
Proceedings of the 24th International Conference on Randomization and …, 2020
62020
Nie można teraz wykonać tej operacji. Spróbuj ponownie później.
Prace 1–20