Sotabase

Career

· Associate Professor, University of Waterloo

Publications (38)

Humanity's Last Exam
Robotics · 2025
284
cited
Separations in query complexity using cheat sheets
Electron. Colloquium Comput. Complex. · 2015
90
cited
Quantum Tokens for Digital Signatures
IACR Cryptology ePrint Archive · 2016
67
cited
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
Symposium on the Theory of Computing · 2020
57
cited
Data stability in clustering: A closer look
Theoretical Computer Science · 2011
37
cited
Symmetries, Graph Properties, and Quantum Speedups
IEEE Annual Symposium on Foundations of Computer Science · 2020
36
cited
Randomized Query Complexity of Sabotaged and Composed Functions
International Colloquium on Automata, Languages and Programming · 2016
33
cited
Low-Sensitivity Functions from Unambiguous Certificates
Information Technology Convergence and Services · 2016
32
cited
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract
IEEE Annual Symposium on Foundations of Computer Science · 2020
22
cited
Separations in Communication Complexity Using Cheat Sheets and Information Complexity
IEEE Annual Symposium on Foundations of Computer Science · 2016
22
cited
A New Minimax Theorem for Randomized Algorithms (Extended Abstract)
IEEE Annual Symposium on Foundations of Computer Science · 2020
18
cited
Unambiguous DNFs and Alon-Saks-Seymour
IEEE Annual Symposium on Foundations of Computer Science · 2021
18
cited
Classical Lower Bounds from Quantum Upper Bounds
IEEE Annual Symposium on Foundations of Computer Science · 2018
15
cited
Quantum Implications of Huang's Sensitivity Theorem
Electron. Colloquium Comput. Complex. · 2020
12
cited
Sculpting Quantum Speedups
Cybersecurity and Cyberforensics Conference · 2015
12
cited
Learning a Classifier when the Labeling Is Known
International Conference on Algorithmic Learning Theory · 2011
11
cited
On query-to-communication lifting for adversary bounds
Cybersecurity and Cyberforensics Conference · 2020
10
cited
The Structure of Promises in Quantum Speedups
Theory of Quantum Computation, Communication, and Cryptography · 2014
8
cited
A Super-Grover Separation Between Randomized and Quantum Query Complexities
Electron. Colloquium Comput. Complex. · 2015
7
cited
Randomised Composition and Small-Bias Minimax
IEEE Annual Symposium on Foundations of Computer Science · 2022
7
cited
Sotabase
Shalev Ben-David | Researcher Profile | Sotabase | Sotabase