Robin Kothari
According to our database^{1},
Robin Kothari
authored at least 31 papers
between 2010 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org
On csauthors.net:
Bibliography
2019
Exponential separation between shallow quantum circuits and unbounded fanin shallow classical circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 2019
Quantum Distinguishing Complexity, ZeroError Algorithms, and Statistical Zero Knowledge.
Proceedings of the 14th Conference on the Theory of Quantum Computation, 2019
2018
Randomized Query Complexity of Sabotaged and Composed Functions.
Theory of Computing, 2018
Quantum algorithms and approximating polynomials for composed functions with shared inputs.
Electronic Colloquium on Computational Complexity (ECCC), 2018
Quantum Algorithm for Simulating Real Time Evolution of Lattice Hamiltonians.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018
Classical Lower Bounds from Quantum Upper Bounds.
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.
SIAM J. Comput., 2017
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.
Electronic Colloquium on Computational Complexity (ECCC), 2017
Separating Quantum Communication and Approximate Rank.
Proceedings of the 32nd Computational Complexity Conference, 2017
2016
Quantum Algorithms for Matrix Multiplication and Product Verification.
Encyclopedia of Algorithms, 2016
Separations in communication complexity using cheat sheets and information complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2016
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.
Algorithmica, 2016
Nearly Optimal Separations Between Communication (or Query) Complexity and Partitions.
Proceedings of the 31st Conference on Computational Complexity, 2016
2015
Nearly optimal separations between communication (or query) complexity and partitions.
Electronic Colloquium on Computational Complexity (ECCC), 2015
Separations in query complexity using cheat sheets.
Electronic Colloquium on Computational Complexity (ECCC), 2015
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015
Separating Decision Tree Complexity from Subcube Partition Complexity.
Proceedings of the Approximation, 2015
2014
Efficient algorithms in quantum query complexity.
PhD thesis, 2014
Exponential improvement in precision for simulating sparse Hamiltonians.
Proceedings of the Symposium on Theory of Computing, 2014
An optimal quantum algorithm for the oracle identification problem.
Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014
2013
A TimeEfficient Quantum Walk for 3Distinctness Using Nested Updates
CoRR, 2013
Dequantizing Readonce Quantum Formulas.
Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013
Easy and Hard Functions for the Boolean Hidden Shift Problem.
Proceedings of the 8th Conference on the Theory of Quantum Computation, 2013
Nested Quantum Walks with Quantum Data Structures.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
TimeEfficient Quantum Walks for 3Distinctness.
Proceedings of the Automata, Languages, and Programming  40th International Colloquium, 2013
2012
Quantum Query Complexity of MinorClosed Graph Properties.
SIAM J. Comput., 2012
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision.
Proceedings of the Automata, Languages, and Programming  39th International Colloquium, 2012
The Quantum Query Complexity of ReadMany Formulas.
Proceedings of the Algorithms  ESA 2012, 2012
2010
Limitations on the simulation of nonsparse Hamiltonians.
Quantum Information & Computation, 2010
Simulating Sparse Hamiltonians with Star Decompositions.
Proceedings of the Theory of Quantum Computation, Communication, and Cryptography, 2010