I am an Assistant Professor at the David R. Cheriton School of Computer Science and the Institute for Quantum Computing at the University of Waterloo. My research interests include computational complexity and quantum computing.
Interests
- Computational Complexity
- Quantum Computing
- Boolean Functions
Education
-
PhD in Electrical Engineering and Computer Science, 2017
Massachusetts Institute of Technology
-
SM in Electrical Engineering and Computer Science, 2014
Massachusetts Institute of Technology
-
BMath in Pure Mathematics and Combinatorics & Optimization, 2011
University of Waterloo
Recent Work
Quickly discover relevant content by filtering publications.
(2021).
Unambiguous DNFs and Alon-Saks-Seymour.
Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS).
(2021).
On Query-to-Communication Lifting for Adversary Bounds.
Proceedings of the 36th Computational Complexity Conference (CCC).
(2020).
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.
Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS).
(2020).
Symmetries, Graph Properties, and Quantum Speedups.
Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS).
(2020).
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem.
Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC).
Contact
- shalev.b@uwaterloo.ca
- Office: DC 3128