About me
I am currently a Senior Researcher at Microsoft Quantum in Redmond, WA.
Area of research: I am a theoretical computer scientist and my primary area of research is quantum algorithms and complexity theory.
I have worked extensively on quantum algorithms for simulating the dynamics of physical systems, which is perhaps the most promising application of quantum computers.
I have also worked on quantum algorithms for linear algebraic, graph theoretic, combinatorial, and machine learning problems, and
on algorithms and lower bounds in (quantum and classical) query complexity, communication complexity, and circuit complexity.
Past positions and education: I was a postdoctoral associate at the Center for Theoretical Physics at MIT. I received an M.Math and Ph.D. at the David R. Cheriton School of Computer Science and Institute for Quantum Computing at the University of Waterloo. I received a B.Tech at the Indian Institute of Technology Bombay.
Service: I have served on the program committees of the following conferences:
FOCS 2020, QIP 2020, QIP 2019, TQC 2018,
QIP 2017


Contact information
Personal email address: ⟨robinrobinkotharicom⟩
This is much easier for me to check and I check this more frequently. Use this for personal or researchrelated or miscellaneous email.
Microsoft email address: ⟨robin.kotharimicrosoftcom⟩
Use this for anything that's Microsoft confidential or Microsoft related (e.g., internships at Microsoft).
My Google Scholar page.
My Microsoft Research profile.
Publications / preprints
All my publications are available on the arXiv.
Unambiguous DNFs from Hex
Shalev BenDavid, Mika Göös, Siddhartha Jain, and Robin Kothari
[arXiv:2102.08348]

Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev BenDavid, Robin Kothari, Shravas Rao, and Avishay Tal
To be presented at the 53rd Annual ACM Symposium on Theory of Computing (STOC 2021).
Presented at the 24rd Annual Conference on Quantum Information Processing (QIP 2021) as a short plenary talk.
[arXiv:2010.12629]
This work subsumes the following older preprint by a subset of the authors:
Quantum Implications of Huang's Sensitivity Theorem
Scott Aaronson, Shalev BenDavid, Robin Kothari, and Avishay Tal
[arXiv:2004.13231]

No quantum speedup over gradient descent for nonsmooth convex optimization
Ankit Garg, Robin Kothari, Praneeth Netrapalli, and Suhail Sherif
Presented at the 12th Innovations in Theoretical Computer Science Conference (ITCS 2021).
Presented at the 24rd Annual Conference on Quantum Information Processing (QIP 2021).
[arXiv:2010.01801]

When Is Amplification Necessary for Composition in Randomized Query Complexity?
Shalev BenDavid, Mika Göös, Robin Kothari, and Thomas Watson
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), Leibniz International Proceedings in Informatics (LIPIcs) 176, pp. 28:1 – 28:16 (2020).
[arXiv:2006.10957] [RANDOM 2020]

Quantum Coupon Collector
Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf
15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 158, pp. 10:1 – 10:17 (2020).
[arXiv:2002.07688] [TQC 2020]

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials
Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler
Presented at the 23rd Annual Conference on Quantum Information Processing (QIP 2020).
35th Computational Complexity Conference (CCC 2020), Leibniz International Proceedings in Informatics (LIPIcs) 169, pp. 7:1 – 7:47 (2020).
[arXiv:1904.08914] [QIP 2020 Video] [CCC 2020]

Exponential separation between shallow quantum circuits and unbounded fanin shallow classical circuits
Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal
Presented at the 22nd Annual Conference on Quantum Information Processing (QIP 2019).
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019), pp. 515–526 (2019).
[arXiv:1906.08890] [STOC 2019]

Quantum distinguishing complexity, zeroerror algorithms, and statistical zero knowledge
Shalev BenDavid and Robin Kothari
14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019).
[arXiv:1902.03660] [TQC 2019] [TQC 2019 Video]

Quantum algorithms and approximating polynomials for composed functions with shared inputs
Mark Bun, Robin Kothari, and Justin Thaler
Proceedings of the 30th ACMSIAM Symposium on Discrete Algorithms (SODA 2019), pp. 662–678 (2019).
[arXiv:1809.02254] [SODA 2019]

Classical lower bounds from quantum upper bounds
Shalev BenDavid, Adam Bouland, Ankit Garg, and Robin Kothari
Presented at the 21th Annual Conference on Quantum Information Processing (QIP 2018).
Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS 2018), pp. 339–349 (2018).
[arXiv:1807.06256] [FOCS 2018]

Quantum algorithm for simulating real time evolution of lattice Hamiltonians
Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low
Presented at the 22nd Annual Conference on Quantum Information Processing (QIP 2019) as a plenary talk (speaker: Jeongwan Haah).
Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS 2018), pp. 350–360 (2018).
[arXiv:1801.03922] [FOCS 2018]

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Mark Bun, Robin Kothari, and Justin Thaler
Presented at the 21th Annual Conference on Quantum Information Processing (QIP 2018) as a plenary talk (speaker: Robin Kothari).
Proceedings of the 50th ACM Symposium on Theory of Computing (STOC 2018), pp. 297–310 (2018).
Theory of Computing , Volume 16(10), pp. 171, 2020.
[arXiv:1710.09079] [ECCC TR17169] [STOC 2018] [Theory of Computing] [QIP 2018 Video]

Separating quantum communication and approximate rank
Anurag Anshu, Shalev BenDavid, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee
To be presented at the 21th Annual Conference on Quantum Information Processing (QIP 2018).
32nd Conference on Computational Complexity (CCC 2017), Leibniz International Proceedings in Informatics (LIPIcs) 79, pp. 24:1–24:33 (2017).
[arXiv:1611.05754] [CCC 2016]

Randomized query complexity of sabotaged and composed functions
Shalev BenDavid and Robin Kothari
43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Leibniz International Proceedings in Informatics (LIPIcs) 55, 60:1–60:14 (2016).
Theory of Computing, Volume 14(5), pp. 127, 2018.
[arXiv:1605.09071] [ECCC TR16087] [ICALP 2016] [Theory of Computing]

Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev BenDavid, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Presented at the 20th Conference on Quantum Information Processing (QIP 2017).
Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 555–564 (2016).
[arXiv:1605.01142] [ECCC TR16072] [FOCS 2016]

Nearly optimal separations between communication (or query) complexity and partitions
Andris Ambainis, Martins Kokainis, and Robin Kothari
31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics (LIPIcs) 50, pp. 4:1–4:14 (2016).
[arXiv:1512.01210]+[arXiv:1512.00661] [ECCC TR15195] [CCC 2016]

Quantum linear systems algorithm with exponentially improved dependence on precision
Andrew M. Childs, Robin Kothari, and Rolando D. Somma
Presented at the 19th Conference on Quantum Information Processing (QIP 2016) as a contributed talk (speaker: Robin Kothari)
SIAM Journal on Computing, 46(6), 1920–1950 (2017).
[arXiv:1511.02306] [SIAM Journal on Computing] [Video from a talk at QuICS] [QIP 2016 Video: Part 1 Part 2 ]

Separations in query complexity using cheat sheets
Scott Aaronson, Shalev BenDavid, and Robin Kothari
Presented at the 19th Conference on Quantum Information Processing (QIP 2016) as a plenary talk (speaker: Shalev BenDavid)
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pp. 863–876 (2016).
[arXiv:1511.01937] [ECCC TR15175] [STOC 2016]

Separating decision tree complexity from subcube partition complexity
Robin Kothari, David RacicotDesloges, and Miklos Santha
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015), Leibniz International Proceedings in Informatics (LIPIcs) 40, pp. 915–930 (2015).
[arXiv:1504.01339] [RANDOM 2015]

Hamiltonian simulation with nearly optimal dependence on all parameters
Dominic W. Berry, Andrew M. Childs, and Robin Kothari
Presented at the 18th Conference on Quantum Information Processing (QIP 2015) as a contributed talk (speaker: Dominic Berry)
Proceedings of the 56th Annual Symposium on Foundations of Computer Science (FOCS 2015), pp. 792–809 (2015).
[arXiv:1501.01715] [FOCS 2015]

Simulating Hamiltonian dynamics with a truncated Taylor series
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Physical Review Letters 114, 090502 (2015)
[arXiv:1412.4687] [PRL]

Exponential improvement in precision for simulating sparse Hamiltonians
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma
Presented at the 17th Workshop on Quantum Information Processing (QIP 2014) as a contributed talk (speaker: Robin Kothari)
Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 283–292 (2014).
Forum of Mathematics, Sigma 5, e8 (2017).
[arXiv:1312.1414] [STOC 2014] [Forum of Mathematics, Sigma]

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), Leibniz International Proceedings in Informatics 25, pp. 482–493 (2014).
[arXiv:1311.7685] [STACS 2014]

Dequantizing Readonce Quantum Formulas
Alessandro Cosentino, Robin Kothari, and Adam Paetznick
8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 80–92 (2013).
[arXiv:1304.5164] [TQC 2013]

Easy and hard functions for the Boolean hidden shift problem
Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler
8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Proceedings in Informatics (LIPIcs) 22, pp. 50–79 (2013).
[arXiv:1304.4642] [TQC 2013]

A TimeEfficient Quantum Walk for 3Distinctness Using Nested Updates
Andrew M. Childs, Stacey Jeffery, Robin Kothari, and Frédéric Magniez
[arXiv:1302.7316]
Merged with arXiv:1302.3143 by Aleksandrs Belovs for ICALP 2013.
Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP 2013), Lecture Notes in Computer Science 7965, pp. 105–122 (2013).
[ICALP 2013]

Nested quantum walks with quantum data structures
Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Presented at the 17th Workshop on Quantum Information Processing (QIP 2014) as a contributed talk, combined with the above paper (arXiv:1302.7316). (speaker: Stacey Jeffery)
Proceedings of the 24th ACMSIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1474–1485 (2013).
[arXiv:1210.1199] [SODA 2013]
 Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
Stacey Jeffery, Robin Kothari, and Frédéric Magniez
Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Lecture Notes in Computer Science 7391, pp. 522–532 (2012).
Algorithmica, 76:1, pp. 1–16 (2016).
[arXiv:1112.5855] [ICALP 2012] [Algorithmica]
 The quantum query complexity of readmany formulas
Andrew M. Childs, Shelby Kimmel, and Robin Kothari
Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012), Lecture Notes in Computer Science 7501, pp. 337–348 (2012).
[arXiv:1112.0548] [ESA 2012]
 Quantum query complexity of minorclosed graph properties
Andrew M. Childs and Robin Kothari
Presented at the 14th Workshop on Quantum Information Processing (QIP 2011) as a contributed talk (speaker: Robin Kothari)
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Leibniz International Proceedings in Informatics 9, pp. 661–672 (2011).
SIAM Journal on Computing, 41(6), 1426–1450 (2012).
[arXiv:1011.1443] [STACS 2011] [QIP 2011: AbstractSlidesVideo] [SIAM Journal on Computing]
 Simulating sparse Hamiltonians with star decompositions
Andrew M. Childs and Robin Kothari
Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), Lecture Notes in Computer Science 6519, pp. 94–103 (2011).
[arXiv:1003.3683] [TQC 2010]
 Limitations on the simulation of nonsparse Hamiltonians
Andrew M. Childs and Robin Kothari
Quantum Information and Computation 10, 669–684 (2010).
[arXiv:0908.4398] [Quantum Information and Computation]
 Dissipation in circuit quantum electrodynamics: lasing and cooling of a lowfrequency oscillator
Julian Hauss, Arkady Fedorov, Stephan André, Valentina Brosco, Carsten Hutter, Robin Kothari, Sunil Yeshwanth, Alexander Shnirman, and Gerd Schön
New Journal of Physics 10 095018 (2008).
[arXiv:0806.1298] [New Journal of Physics]
Theses / surveys
 Quantum algorithms for matrix multiplication and product verification
Robin Kothari and Ashwin Nayak
In MingYang Kao, editor, Encyclopedia of Algorithms, pp. 1673–1677. Springer New York, 2016.
[Springer] [Draft PDF]
 Efficient algorithms in quantum query complexity
Robin Kothari
PhD thesis (2014)
[University of Waterloo's Institutional Repository] [PDF]
In this thesis we provide new upper and lower bounds on the quantum query complexity of a diverse set of problems. Specifically, we study quantum algorithms for Hamiltonian simulation, matrix multiplication, oracle identification, and graphproperty recognition. For the Hamiltonian simulation problem, we provide a quantum algorithm with query complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Our algorithm is based on a new quantum algorithm for implementing unitary matrices that can be written as linear combinations of efficiently implementable unitary gates. This algorithm uses a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. In the oracle identification problem, we are given oracle access to an unknown Nbit string x promised to belong to a known set of size M, and our task is to identify x. We present the first quantum algorithm for the problem that is optimal in its dependence on N and M. Our algorithm is based on ideas from classical learning theory and a new composition theorem for solutions of the filtered gamma_2norm semidefinite program. We then study the quantum query complexity of matrix multiplication and related problems over rings, semirings, and the Boolean semiring in particular. Our main result is an outputsensitive algorithm for Boolean matrix multiplication that multiplies two n x n Boolean matrices with query complexity O(n sqrt{l}), where l is the sparsity of the output matrix. The algorithm is based on a reduction to the graph collision problem and a new algorithm for graph collision. Finally, we study the quantum query complexity of minorclosed graph properties and show that most minorclosed propertiesthose that cannot be characterized by a finite set of forbidden subgraphshave quantum query complexity Theta(n^{3/2}) and those that do have such a characterization can be solved strictly faster, with o(n^{3/2}) queries. Our lower bound is based on a detailed analysis of the structure of minorclosed properties with respect to forbidden topological minors and forbidden subgraphs. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraphfinding problems.
 Efficient simulation of Hamiltonians
Robin Kothari
Master's thesis (2010)
[University of Waterloo's Institutional Repository] [PDF]
The problem considered in this thesis is the following: We are given a Hamiltonian H and time t, and our goal is to approximately implement the unitary oper$ algorithm. We present an efficient algorithm for simulating sparse Hamiltonians. In terms of the maximum degree d and dimension N of the space on which the $ (d^2(d+log^* N)Ht)^{1+o(1)} queries. This improves the complexity of the sparse Hamiltonian simulation algorithm of Berry, Ahokas, Cleve, and Sanders, w$ N)Ht)^{1+o(1)}. In terms of the parameter t, these algorithms are essentially optimal due to a nofastforwarding theorem. In the second part of this t$ and show significant limitations on their simulation. We generalize the nofastforwarding theorem to dense Hamiltonians, and rule out generic simulations $ not a unique measure of the size of a dense Hamiltonian H. We also present a stronger limitation ruling out the possibility of generic simulations taking ti$ simulations based on discretetime quantum walks cannot be dramatically improved in general. We also show some positive results about simulating structured $