Shalev Ben-David

66 papers A* 12A 5B 1Journal 43Unranked 4

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