Publications

Unambiguous DNFs and Alon-Saks-Seymour
Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Cite DOI
On Query-to-Communication Lifting for Adversary Bounds
Anurag Anshu, Shalev Ben-David, Srijita Kundu
Cite DOI
Symmetries, Graph Properties, and Quantum Speedups
Shalev Ben-David, Andrew M. Childs, Andras Gilyen, William Kretschmer, Supartha Podder, Daochen Wang
Cite DOI
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions
Shalev Ben-David, Eric Blais
Cite DOI
A New Minimax Theorem for Randomized Algorithms
Shalev Ben-David, Eric Blais
Cite DOI
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Cite DOI
When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
Cite DOI
Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge
Shalev Ben-David, Robin Kothari
Cite DOI
Classical Lower Bounds from Quantum Upper Bounds
Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari
Cite DOI
Randomized Query Complexity of Sabotaged and Composed Functions
Shalev Ben-David, Robin Kothari
Cite DOI
Quantum Speedups in Query Complexity
Shalev Ben-David
PDF Cite
Separating Quantum Communication and Approximate Rank
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Cite DOI
Low-Sensitivity Functions from Unambiguous Certificates
Shalev Ben-David, Pooya Hatami, Avishay Tal
Cite DOI
Separations in Communication Complexity Using Cheat Sheets and Information Complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Cite DOI
The Structure of Promises in Quantum Speedups
Shalev Ben-David
Cite DOI
Quantum Tokens for Digital Signatures
Shalev Ben-David, Or Sattath
Cite
On Rota's Conjecture and Nested Separations in Matroids
Shalev Ben-David, Jim Geelen
Cite DOI
Separations in Query Complexity Using Cheat Sheets
Scott Aaronson, Shalev Ben-David, Robin Kothari
Cite DOI
Sculpting Quantum Speedups
Scott Aaronson, Shalev Ben-David
Cite DOI
A super-Grover separation between randomized and quantum query complexities
Shalev Ben-David
Cite
Data Stability in Clustering: A Closer Look
Shalev Ben-David, Lev Reyzin
Cite DOI
The Structure of Promises in Quantum Speedups
Shalev Ben-David
PDF Cite
The Approximability and Integrality Gap of Interval Stabbing and Independence Problems
Shalev Ben-David, Elyot Grant, Will Ma, Malcolm Sharpe
PDF Cite
Learning a Classifier when the Labeling Is Known
Shalev Ben-David, Shai Ben-David
Cite DOI
Supporting Ranking Queries on Uncertain and Incomplete Data
Mohamed A. Soliman, Ihab F. Ilyas, Shalev Ben-David
Cite DOI