Shalev Ben-David

ORCID

Publication Activity (10 Years)

Years Active: 2010-2024
Publications (10 Years): 48

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

FOCS

Computational Complexity Conference

Massachusetts Institute of Technology, Cambridge, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, USA

PHD

Publications

Shalev Ben-David, Srijita Kundu
Oracle separation of QMA and QCMA with bounded adaptivity. CoRR (2024)
Shalev Ben-David, Srijita Kundu
Oracle Separation of QMA and QCMA with Bounded Adaptivity. ICALP (2024)
Shalev Ben-David, Or Sattath
Quantum Tokens for Digital Signatures. Quantum 7 (2023)
Shalev Ben-David, Eric Blais
A New Minimax Theorem for Randomized Algorithms. J. ACM 70 (6) (2023)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. Electron. Colloquium Comput. Complex. (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. FOCS (2022)
Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs and Alon-Saks-Seymour. FOCS (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. CoRR (2022)
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs from Hex. CoRR (2021)
Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs from Hex. Electron. Colloquium Comput. Complex. 28 (2021)
Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs and Alon-Saks-Seymour. FOCS (2021)
Anurag Anshu, Shalev Ben-David, Srijita Kundu
On Query-To-Communication Lifting for Adversary Bounds. Computational Complexity Conference (2021)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. STOC (2021)
Shalev Ben-David, Eric Blais
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions. CoRR (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
Symmetries, graph properties, and quantum speedups. CoRR (2020)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? APPROX-RANDOM (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. Electron. Colloquium Comput. Complex. 27 (2020)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? CoRR (2020)
Shalev Ben-David, Eric Blais
A New Minimax Theorem for Randomized Algorithms (Extended Abstract). FOCS (2020)
Shalev Ben-David, Eric Blais
A New Minimax Theorem for Randomized Algorithms. CoRR (2020)
Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang
Symmetries, Graph Properties, and Quantum Speedups. FOCS (2020)
Shalev Ben-David, Eric Blais
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract. FOCS (2020)
Shalev Ben-David, Supartha Podder
How symmetric is too symmetric for large quantum speedups? CoRR (2020)
Anurag Anshu, Shalev Ben-David, Srijita Kundu
On Query-to-Communication Lifting for Adversary Bounds. CoRR (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Shalev Ben-David, Robin Kothari
Quantum distinguishing complexity, zero-error algorithms, and statistical zero knowledge. CoRR (2019)
Shalev Ben-David, Robin Kothari
Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. TQC (2019)
Shalev Ben-David, Robin Kothari
Randomized Query Complexity of Sabotaged and Composed Functions. Theory Comput. 14 (1) (2018)
Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari
Classical Lower Bounds from Quantum Upper Bounds. FOCS (2018)
Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari
Classical lower bounds from quantum upper bounds. CoRR (2018)
Shalev Ben-David, Pooya Hatami, Avishay Tal
Low-Sensitivity Functions from Unambiguous Certificates. ITCS (2017)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Separating Quantum Communication and Approximate Rank. Computational Complexity Conference (2017)
Shalev Ben-David, Or Sattath
Quantum Tokens for Digital Signatures. IACR Cryptol. ePrint Arch. 2017 (2017)
Shalev Ben-David, Robin Kothari
Randomized query complexity of sabotaged and composed functions. CoRR (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Shalev Ben-David, Robin Kothari
Randomized Query Complexity of Sabotaged and Composed Functions. ICALP (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS (2016)
Shalev Ben-David, Robin Kothari
Randomized query complexity of sabotaged and composed functions. Electron. Colloquium Comput. Complex. 23 (2016)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. STOC (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. CoRR (2016)
Scott Aaronson, Shalev Ben-David
Sculpting Quantum Speedups. Computational Complexity Conference (2016)
Shalev Ben-David
The Structure of Promises in Quantum Speedups. TQC (2016)
Shalev Ben-David, Or Sattath
Quantum Tokens for Digital Signatures. CoRR (2016)
Shalev Ben-David
Low-Sensitivity Functions from Unambiguous Certificates. Electron. Colloquium Comput. Complex. 23 (2016)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Separating quantum communication and approximate rank. CoRR (2016)
Shalev Ben-David
Low-Sensitivity Functions from Unambiguous Certificates. CoRR (2016)
Shalev Ben-David, Jim Geelen
On Rota's Conjecture and nested separations in matroids. J. Comb. Theory, Ser. B 119 (2016)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. CoRR (2015)
Scott Aaronson, Shalev Ben-David
Sculpting Quantum Speedups. Electron. Colloquium Comput. Complex. 22 (2015)
Scott Aaronson, Shalev Ben-David
Sculpting Quantum Speedups. CoRR (2015)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. Electron. Colloquium Comput. Complex. 22 (2015)
Shalev Ben-David
A Super-Grover Separation Between Randomized and Quantum Query Complexities. CoRR (2015)
Shalev Ben-David
A Super-Grover Separation Between Randomized and Quantum Query Complexities. Electron. Colloquium Comput. Complex. 22 (2015)
Shalev Ben-David, Lev Reyzin
Data stability in clustering: A closer look. Theor. Comput. Sci. 558 (2014)
Shalev Ben-David
The Structure of Promises in Quantum Speedups. CoRR (2014)
Shalev Ben-David, Elyot Grant, Will Ma, Malcolm Sharpe
The Approximability and Integrality Gap of Interval Stabbing and Independence Problems. CCCG (2012)
Shalev Ben-David, Shai Ben-David
Learning a Classifier when the Labeling Is Known. ALT (2011)
Mohamed A. Soliman, Ihab F. Ilyas, Shalev Ben-David
Supporting ranking queries on uncertain and incomplete data. VLDB J. 19 (4) (2010)

Shalev Ben-David.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shalev Ben-David