About me

my picture

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

My Microsoft Research profile. My Google Scholar page.

Microsoft email (use for Microsoft-related or research-related email): ⟨robin.kothari|microsoft|com⟩
Personal email (use for personal or research-related email): ⟨robin|robinkothari|com⟩

Publications / preprints

All my publications are available on the arXiv.
  1. Quantum Implications of Huang's Sensitivity Theorem
    Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal
    [arXiv:2004.13231]

  2. Quantum Coupon Collector
    Srinivasan Arunachalam, Aleksandrs Belovs, Andrew M. Childs, Robin Kothari, Ansis Rosmanis, and Ronald de Wolf
    In the proceedinds of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020).
    [arXiv:2002.07688] [TQC 2020]

  3. 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).
    To be presented at Computational Complexity Conference (CCC 2020).
    [arXiv:1904.08914] [QIP 2020 Video]

  4. Exponential separation between shallow quantum circuits and unbounded fan-in 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]

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

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

  7. Classical lower bounds from quantum upper bounds
    Shalev Ben-David, 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]

  8. 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]

  9. 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).
    [arXiv:1710.09079] [ECCC TR17-169] [STOC 2018] [QIP 2018 Video]

  10. Separating quantum communication and approximate rank
    Anurag Anshu, Shalev Ben-David, 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]

  11. Randomized query complexity of sabotaged and composed functions
    Shalev Ben-David 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. 1-27, 2018.
    [arXiv:1605.09071] [ECCC TR16-087] [ICALP 2016] [Theory of Computing]

  12. 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
    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 TR16-072] [FOCS 2016]

  13. 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 TR15-195] [CCC 2016]

  14. 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 ]

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

  16. Separating decision tree complexity from subcube partition complexity
    Robin Kothari, David Racicot-Desloges, 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]

  17. 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]

  18. 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]

  19. 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]

  20. 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]

  21. Dequantizing Read-once 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]

  22. 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]

  23. A Time-Efficient Quantum Walk for 3-Distinctness 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]

  24. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 1474–1485 (2013).
    [arXiv:1210.1199] [SODA 2013]

  25. 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]

  26. The quantum query complexity of read-many 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]

  27. Quantum query complexity of minor-closed 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: Abstract|Slides|Video] [SIAM Journal on Computing]

  28. 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]

  29. Limitations on the simulation of non-sparse Hamiltonians
    Andrew M. Childs and Robin Kothari
    Quantum Information and Computation 10, 669–684 (2010).
    [arXiv:0908.4398] [Quantum Information and Computation]

  30. Dissipation in circuit quantum electrodynamics: lasing and cooling of a low-frequency 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