Robin Kothari

ORCID

Publication Activity (10 Years)

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

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

FOCS

STOC

University of Waterloo, Ontario, Canada (PHD)

Education History

University of Waterloo, Ontario, Canada

PHD

Publications

Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush
Quartic quantum speedups for planted inference. CoRR (2024)
Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe
. FOCS (2023)
Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
Query-optimal estimation of unitary channels in diamond distance. FOCS (2023)
Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. SIAM J. Comput. 52 (6) (2023)
Robin Kothari, Ryan O'Donnell
Mean estimation when you have the source code; or, quantum Monte Carlo methods. SODA (2023)
Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang
Query-optimal estimation of unitary channels in diamond distance. CoRR (2023)
Robin Kothari, Ryan O'Donnell
Mean estimation when you have the source code; or, quantum Monte Carlo methods. CoRR (2022)
Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang
Quantum divide and conquer. CoRR (2022)
Jeongwan Haah, Robin Kothari, Ewin Tang
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. FOCS (2022)
Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, Robin Kothari
Unambiguous DNFs and Alon-Saks-Seymour. FOCS (2022)
Jeongwan Haah, Robin Kothari, Ewin Tang
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. CoRR (2021)
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)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization. ITCS (2021)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness. NeurIPS (2021)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum 5 (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)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness. CoRR (2021)
Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, Martin Roetteler
Quantum Algorithms for Reinforcement Learning with a Generative Model. CoRR (2021)
Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, Martin Roetteler
Quantum algorithms for reinforcement learning with a generative model. ICML (2021)
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)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Computational Complexity Conference (2020)
Shalev Ben-David, Mika Göös, Robin Kothari, Thomas Watson
When Is Amplification Necessary for Composition in Randomized Query Complexity? APPROX-RANDOM (2020)
Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif
No quantum speedup over gradient descent for non-smooth convex optimization. CoRR (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)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
Quantum Coupon Collector. CoRR (2020)
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf
Quantum Coupon Collector. TQC (2020)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. 16 (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. STOC (2019)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA (2019)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. CoRR (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. 26 (2019)
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)
Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal
Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits. Electron. Colloquium Comput. Complex. 26 (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR (2019)
Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians. FOCS (2018)
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)
Mark Bun, Robin Kothari, Justin Thaler
The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC (2018)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. 25 (2018)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR (2018)
Shalev Ben-David, Adam Bouland, Ankit Garg, Robin Kothari
Classical lower bounds from quantum upper bounds. CoRR (2018)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR (2017)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. 24 (2017)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Separating Quantum Communication and Approximate Rank. Computational Complexity Conference (2017)
Andrew M. Childs, Robin Kothari, Rolando D. Somma
Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision. SIAM J. Comput. 46 (6) (2017)
Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. Algorithmica 76 (1) (2016)
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)
Andris Ambainis, Martins Kokainis, Robin Kothari
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions. Computational Complexity Conference (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)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Separating quantum communication and approximate rank. CoRR (2016)
Robin Kothari
Nearly optimal separations between communication (or query) complexity and partitions. Electron. Colloquium Comput. Complex. 22 (2015)
Robin Kothari, David Racicot-Desloges, Miklos Santha
Separating Decision Tree Complexity from Subcube Partition Complexity. APPROX-RANDOM (2015)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. CoRR (2015)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. Electron. Colloquium Comput. Complex. 22 (2015)
Robin Kothari, David Racicot-Desloges, Miklos Santha
Separating decision tree complexity from subcube partition complexity. CoRR (2015)
Robin Kothari
Nearly optimal separations between communication (or query) complexity and partitions. CoRR (2015)
Dominic W. Berry, Andrew M. Childs, Robin Kothari
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. FOCS (2015)
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma
Exponential improvement in precision for simulating sparse Hamiltonians. STOC (2014)
Robin Kothari
An optimal quantum algorithm for the oracle identification problem. STACS (2014)
Alessandro Cosentino, Robin Kothari, Adam Paetznick
Dequantizing read-once quantum formulas CoRR (2013)
Alessandro Cosentino, Robin Kothari, Adam Paetznick
Dequantizing Read-once Quantum Formulas. TQC (2013)
Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler
Easy and hard functions for the Boolean hidden shift problem CoRR (2013)
Stacey Jeffery, Robin Kothari, Frédéric Magniez
Nested Quantum Walks with Quantum Data Structures. SODA (2013)
Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates CoRR (2013)
Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler
Easy and Hard Functions for the Boolean Hidden Shift Problem. TQC (2013)
Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez
Time-Efficient Quantum Walks for 3-Distinctness. ICALP (1) (2013)
Robin Kothari
An optimal quantum algorithm for the oracle identification problem. CoRR (2013)
Stacey Jeffery, Robin Kothari, Frédéric Magniez
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. ICALP (1) (2012)
Andrew M. Childs, Robin Kothari
Quantum Query Complexity of Minor-Closed Graph Properties. SIAM J. Comput. 41 (6) (2012)
Andrew M. Childs, Shelby Kimmel, Robin Kothari
The Quantum Query Complexity of Read-Many Formulas. ESA (2012)
Andrew M. Childs, Shelby Kimmel, Robin Kothari
The quantum query complexity of read-many formulas CoRR (2011)
Andrew M. Childs, Robin Kothari
Quantum query complexity of minor-closed graph properties. STACS (2011)
Andrew M. Childs, Robin Kothari
Quantum query complexity of minor-closed graph properties CoRR (2010)
Andrew M. Childs, Robin Kothari
Limitations on the simulation of non-sparse Hamiltonians. Quantum Inf. Comput. 10 (7&8) (2010)
Andrew M. Childs, Robin Kothari
Simulating Sparse Hamiltonians with Star Decompositions. TQC (2010)

Robin Kothari.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Robin Kothari