Robin Kothari

According to our database, Robin Kothari authored at least 46 papers between 2010 and 2024.

Collaborative distances:

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

2024

Quartic quantum speedups for planted inference.

Alexander Schmidhuber, Ryan O'Donnell, Robin Kothari, Ryan Babbush

CoRR, 2024

2023

Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians.

Jeongwan Haah, Matthew B. Hastings, Robin Kothari, Guang Hao Low

SIAM J. Comput., December, 2023

Mean estimation when you have the source code; or, quantum Monte Carlo methods.

Robin Kothari, Ryan O'Donnell

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Query-optimal estimation of unitary channels in diamond distance.

Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Exponential quantum speedup in simulating coupled classical oscillators^*.

Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Quantum divide and conquer.

Andrew M. Childs, Robin Kothari, Matt Kovacs-Deak, Aarthi Sundaram, Daochen Wang

CoRR, 2022

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states.

Jeongwan Haah, Robin Kothari, Ewin Tang

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Quantum algorithms and approximating polynomials for composed functions with shared inputs.

Mark Bun, Robin Kothari, Justin Thaler

Quantum, 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

Near-Optimal Lower Bounds For Convex Optimization For All Orders of Smoothness.

Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

No Quantum Speedup over Gradient Descent for Non-Smooth Convex Optimization.

Ankit Garg, Robin Kothari, Praneeth Netrapalli, Suhail Sherif

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Quantum algorithms for reinforcement learning with a generative model.

Daochen Wang, Aarthi Sundaram, Robin Kothari, Ashish Kapoor, Martin Roetteler

Proceedings of the 38th International Conference on Machine Learning, 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

2020

Quantum Implications of Huang's Sensitivity Theorem.

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

Electron. Colloquium Comput. Complex., 2020

Quantum Coupon Collector.

Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, Ronald de Wolf

Proceedings of the 15th Conference on the Theory of Quantum Computation, 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

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.

Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal

Electron. Colloquium Comput. Complex., 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

Electron. Colloquium Comput. Complex., 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 Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision.

Andrew M. Childs, Robin Kothari, Rolando D. Somma

SIAM J. Comput., 2017

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.

Mark Bun, Robin Kothari, Justin Thaler

Electron. Colloquium Comput. Complex., 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

Quantum Algorithms for Matrix Multiplication and Product Verification.

Robin Kothari, Ashwin Nayak

Encyclopedia of Algorithms, 2016

Randomized query complexity of sabotaged and composed functions.

Shalev Ben-David, Robin Kothari

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

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.

Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez

Algorithmica, 2016

Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions.

Andris Ambainis, Martins Kokainis, Robin Kothari

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Nearly optimal separations between communication (or query) complexity and partitions.

Robin Kothari

Electron. Colloquium Comput. Complex., 2015

Separations in query complexity using cheat sheets.

Scott Aaronson, Shalev Ben-David, Robin Kothari

Electron. Colloquium Comput. Complex., 2015

Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters.

Dominic W. Berry, Andrew M. Childs, Robin Kothari

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Separating Decision Tree Complexity from Subcube Partition Complexity.

Robin Kothari, David Racicot-Desloges, Miklos Santha

Proceedings of the Approximation, 2015

2014

Efficient algorithms in quantum query complexity.

Robin Kothari

PhD thesis, 2014

Exponential improvement in precision for simulating sparse Hamiltonians.

Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, Rolando D. Somma

Proceedings of the Symposium on Theory of Computing, 2014

An optimal quantum algorithm for the oracle identification problem.

Robin Kothari

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

2013

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates

Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

CoRR, 2013

Dequantizing Read-once Quantum Formulas.

Alessandro Cosentino, Robin Kothari, Adam Paetznick

Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Easy and Hard Functions for the Boolean Hidden Shift Problem.

Andrew M. Childs, Robin Kothari, Maris Ozols, Martin Roetteler

Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013

Nested Quantum Walks with Quantum Data Structures.

Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Time-Efficient Quantum Walks for 3-Distinctness.

Aleksandrs Belovs, Andrew M. Childs, Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Quantum Query Complexity of Minor-Closed Graph Properties.

Andrew M. Childs, Robin Kothari

SIAM J. Comput., 2012

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.

Stacey Jeffery, Robin Kothari, Frédéric Magniez

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

The Quantum Query Complexity of Read-Many Formulas.

Andrew M. Childs, Shelby Kimmel, Robin Kothari

Proceedings of the Algorithms - ESA 2012, 2012

2010

Limitations on the simulation of non-sparse Hamiltonians.

Andrew M. Childs, Robin Kothari

Quantum Inf. Comput., 2010

Simulating Sparse Hamiltonians with Star Decompositions.

Andrew M. Childs, Robin Kothari

Proceedings of the Theory of Quantum Computation, Communication, and Cryptography, 2010