Robin Kothari - RankMe

94 papers A* 22A 7Journal 53Unranked 10

Year	Rank	Type	Title / Venue / Authors
2026	A*	`conf`	Quantum State Preparation with Optimal T-Count. SODA David Gosset, Robin Kothari, Kewen Wu
2025	J	`jnl`	A simplified version of the quantum OTOC CoRR Robbie King, Robin Kothari, Ryan Babbush, Sergio Boixo, Kostyantyn Kechedzhi, Thomas E. O'Brien, Vadim Smelyanskiy
2025	J	`jnl`	No exponential quantum speedup for SIS CoRR Robin Kothari, Ryan O'Donnell, Kewen Wu
2025	J	`jnl`	Quantum Divide and Conquer. ACM Trans. Quantum Comput. Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang
2025	A*	`conf`	Quartic quantum speedups for planted inference. SODA Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
2025	A*	`conf`	Triply efficient shadow tomography. SODA Robbie King, David Gosset, Robin Kothari, Ryan Babbush
2025	—	`conf`	Uniformity Testing When You Have the Source Code. TQC Clément L. Canonne, Robin Kothari, Ryan O'Donnell
2024	J	`jnl`	Quartic quantum speedups for planted inference. CoRR Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
2024	J	`jnl`	Uniformity testing when you have the source code. CoRR Clément L. Canonne, Robin Kothari, Ryan O'Donnell
2023	A*	`conf`	Exponential quantum speedup in simulating coupled classical oscillators FOCS Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe
2023	A*	`conf`	Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA Robin Kothari, Ryan O'Donnell
2023	J	`jnl`	Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. SIAM J. Comput. Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low
2023	A*	`conf`	Query-optimal estimation of unitary channels in diamond distance. FOCS Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
2023	J	`jnl`	Query-optimal estimation of unitary channels in diamond distance. CoRR Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
2022	J	`jnl`	Mean estimation when you have the source code; or, quantum Monte Carlo methods. CoRR Robin Kothari, Ryan O'Donnell
2022	A*	`conf`	Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. FOCS Jeongwan Haah, Robin Kothari, Ewin Tang
2022	J	`jnl`	Quantum divide and conquer. CoRR Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang
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`	Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness. NeurIPS Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
2021	J	`jnl`	Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness. CoRR Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
2021	A	`conf`	No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. ITCS Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
2021	J	`jnl`	Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. CoRR Jeongwan Haah, Robin Kothari, Ewin Tang
2021	J	`jnl`	Quantum Algorithms for Reinforcement Learning with a Generative Model. CoRR Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, Martin Roetteler
2021	J	`jnl`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum Mark Bun, Robin Kothari, Justin Thaler
2021	A*	`conf`	Quantum algorithms for reinforcement learning with a generative model. ICML Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, Martin Roetteler
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	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`	No quantum speedup over gradient descent for non-smooth convex optimization. CoRR Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
2020	—	`conf`	Quantum Coupon Collector. TQC Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
2020	J	`jnl`	Quantum Coupon Collector. CoRR Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
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`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CCC Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2020	J	`jnl`	The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. Mark Bun, Robin Kothari, Justin Thaler
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	A*	`conf`	Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019	J	`jnl`	Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. CoRR Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019	J	`jnl`	Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Electron. Colloquium Comput. Complex. Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
2019	—	`conf`	Quantum Distinguishing Complexity, Zero-Error Algorithms, and Statistical Zero Knowledge. TQC Shalev Ben-David, Robin Kothari
2019	J	`jnl`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2019	J	`jnl`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2019	A*	`conf`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA Mark Bun, Robin Kothari, Justin Thaler
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	A*	`conf`	Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. FOCS Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low
2018	J	`jnl`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR Mark Bun, Robin Kothari, Justin Thaler
2018	J	`jnl`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. Mark Bun, Robin Kothari, Justin Thaler
2018	J	`jnl`	Randomized Query Complexity of Sabotaged and Composed Functions. Theory Comput. Shalev Ben-David, Robin Kothari
2018	A*	`conf`	The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC Mark Bun, Robin Kothari, Justin Thaler
2017	J	`jnl`	Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision. SIAM J. Comput. Andrew M. Childs, Robin Kothari, Rolando D. Somma
2017	A	`conf`	Separating Quantum Communication and Approximate Rank. CCC Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
2017	J	`jnl`	The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR Mark Bun, Robin Kothari, Justin Thaler
2017	J	`jnl`	The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. Mark Bun, Robin Kothari, Justin Thaler
2016	J	`jnl`	Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. Algorithmica Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez
2016	A	`conf`	Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. CCC Andris Ambainis, Martins Kokainis, Robin Kothari
2016	—	`ch.`	Quantum Algorithms for Matrix Multiplication and Product Verification. Encyclopedia of Algorithms Robin Kothari, Ashwin Nayak
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	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
2015	A*	`conf`	Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. FOCS Dominic W. Berry, Andrew M. Childs, Robin Kothari
2015	J	`jnl`	Nearly optimal separations between communication (or query) complexity and partitions. CoRR Robin Kothari
2015	J	`jnl`	Nearly optimal separations between communication (or query) complexity and partitions. Electron. Colloquium Comput. Complex. Robin Kothari
2015	—	`conf`	Separating Decision Tree Complexity from Subcube Partition Complexity. APPROX-RANDOM Robin Kothari, David Racicot-Desloges, Miklos Santha
2015	J	`jnl`	Separating decision tree complexity from subcube partition complexity. CoRR Robin Kothari, David Racicot-Desloges, Miklos Santha
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	A	`conf`	An optimal quantum algorithm for the oracle identification problem. STACS Robin Kothari
2014	—	`—`	Efficient algorithms in quantum query complexity. Robin Kothari
2014	A*	`conf`	Exponential improvement in precision for simulating sparse Hamiltonians. STOC Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma
2013	J	`jnl`	A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates CoRR Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
2013	J	`jnl`	An optimal quantum algorithm for the oracle identification problem. CoRR Robin Kothari
2013	—	`conf`	Dequantizing Read-once Quantum Formulas. TQC Alessandro Cosentino, Robin Kothari, Adam Paetznick
2013	J	`jnl`	Dequantizing read-once quantum formulas CoRR Alessandro Cosentino, Robin Kothari, Adam Paetznick
2013	—	`conf`	Easy and Hard Functions for the Boolean Hidden Shift Problem. TQC Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler
2013	J	`jnl`	Easy and hard functions for the Boolean hidden shift problem CoRR Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler
2013	A*	`conf`	Nested Quantum Walks with Quantum Data Structures. SODA Stacey Jeffery, Robin Kothari, Frédéric Magniez
2013	—	`conf`	Time-Efficient Quantum Walks for 3-Distinctness. ICALP (1) Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
2012	—	`conf`	Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. ICALP (1) Stacey Jeffery, Robin Kothari, Frédéric Magniez
2012	J	`jnl`	Quantum Query Complexity of Minor-Closed Graph Properties. SIAM J. Comput. Andrew M. Childs, Robin Kothari
2012	A	`conf`	The Quantum Query Complexity of Read-Many Formulas. ESA Andrew M. Childs, Shelby Kimmel, Robin Kothari
2011	A	`conf`	Quantum query complexity of minor-closed graph properties. STACS Andrew M. Childs, Robin Kothari
2011	J	`jnl`	The quantum query complexity of read-many formulas CoRR Andrew M. Childs, Shelby Kimmel, Robin Kothari
2010	J	`jnl`	Limitations on the simulation of non-sparse Hamiltonians. Quantum Inf. Comput. Andrew M. Childs, Robin Kothari
2010	J	`jnl`	Quantum query complexity of minor-closed graph properties CoRR Andrew M. Childs, Robin Kothari
2010	—	`conf`	Simulating Sparse Hamiltonians with Star Decompositions. TQC Andrew M. Childs, Robin Kothari