Shalev Ben-David

According to our database, Shalev Ben-David authored at least 34 papers between 2010 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Oracle Separations for the Quantum-Classical Polynomial Hierarchy.

Avantika Agarwal, Shalev Ben-David

CoRR, 2024

Separations in query complexity for total search problems.

Shalev Ben-David, Srijita Kundu

CoRR, 2024

Oracle Separation of QMA and QCMA with Bounded Adaptivity.

Shalev Ben-David, Srijita Kundu

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

A New Minimax Theorem for Randomized Algorithms.

Shalev Ben-David, Eric Blais

J. ACM, December, 2023

Quantum Tokens for Digital Signatures.

Shalev Ben-David, Or Sattath

Quantum, January, 2023

2022

Randomised Composition and Small-Bias Minimax.

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

Electron. Colloquium Comput. Complex., 2022

2021

Unambiguous DNFs from Hex.

Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

Electron. Colloquium Comput. Complex., 2021

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem.

Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Unambiguous DNFs and Alon-Saks-Seymour.

Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

On Query-To-Communication Lifting for Adversary Bounds.

Anurag Anshu, Shalev Ben-David, Srijita Kundu

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Quantum Implications of Huang's Sensitivity Theorem.

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.

Shalev Ben-David, Eric Blais

CoRR, 2020

How symmetric is too symmetric for large quantum speedups?

Shalev Ben-David, Supartha Podder

CoRR, 2020

Symmetries, Graph Properties, and Quantum Speedups.

Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, Daochen Wang

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

A New Minimax Theorem for Randomized Algorithms (Extended Abstract).

Shalev Ben-David, Eric Blais

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract.

Shalev Ben-David, Eric Blais

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson

Proceedings of the Approximation, 2020

2019

Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge.

Shalev Ben-David, Robin Kothari

Proceedings of the 14th Conference on the Theory of Quantum Computation, 2019

2018

Classical Lower Bounds from Quantum Upper Bounds.

Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Quantum speedups in query complexity.

Shalev Ben-David

PhD thesis, 2017

Low-Sensitivity Functions from Unambiguous Certificates.

Shalev Ben-David, Pooya Hatami, Avishay Tal

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Separating Quantum Communication and Approximate Rank.

Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

On Rota's Conjecture and nested separations in matroids.

Shalev Ben-David, Jim Geelen

J. Comb. Theory B, 2016

Randomized query complexity of sabotaged and composed functions.

Shalev Ben-David, Robin Kothari

Electron. Colloquium Comput. Complex., 2016

Low-Sensitivity Functions from Unambiguous Certificates.

Shalev Ben-David

Electron. Colloquium Comput. Complex., 2016

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

Electron. Colloquium Comput. Complex., 2016

The Structure of Promises in Quantum Speedups.

Shalev Ben-David

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

2015

A Super-Grover Separation Between Randomized and Quantum Query Complexities.

Shalev Ben-David

Electron. Colloquium Comput. Complex., 2015

Separations in query complexity using cheat sheets.

Scott Aaronson, Shalev Ben-David, Robin Kothari

Electron. Colloquium Comput. Complex., 2015

Sculpting Quantum Speedups.

Scott Aaronson, Shalev Ben-David

Electron. Colloquium Comput. Complex., 2015

2014

Data stability in clustering: A closer look.

Shalev Ben-David, Lev Reyzin

Theor. Comput. Sci., 2014

2012

The Approximability and Integrality Gap of Interval Stabbing and Independence Problems.

Shalev Ben-David, Elyot Grant, Will Ma, Malcolm Sharpe

Proceedings of the 24th Canadian Conference on Computational Geometry, 2012

2011

Learning a Classifier when the Labeling Is Known.

Shalev Ben-David, Shai Ben-David

Proceedings of the Algorithmic Learning Theory - 22nd International Conference, 2011

2010

Supporting ranking queries on uncertain and incomplete data.

Mohamed A. Soliman, Ihab F. Ilyas, Shalev Ben-David

VLDB J., 2010