Robin Kothari

According to our database1, Robin Kothari authored at least 31 papers between 2010 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Exponential separation between shallow quantum circuits and unbounded fan-in 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, Zero-Error 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 Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates
CoRR, 2013

Dequantizing Read-once 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 Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Time-Efficient Quantum Walks for 3-Distinctness.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012
Quantum Query Complexity of Minor-Closed 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 Read-Many Formulas.
Proceedings of the Algorithms - ESA 2012, 2012

2010
Limitations on the simulation of non-sparse Hamiltonians.
Quantum Information & Computation, 2010

Simulating Sparse Hamiltonians with Star Decompositions.
Proceedings of the Theory of Quantum Computation, Communication, and Cryptography, 2010


  Loading...