Troy Lee
Principal Investigator
Troy Lee

Short bio

Troy Lee is a Nanyang Associate Professor at Nanyang Technological University and a Principal Investigator at CQT. He received his Bachelors degree with honors in mathematics from the California Institute of Technology in 2000. From there, he went to the University of Amsterdam, for both Masters (2001) and PhD (2006) degrees, writing a thesis on Kolmogorov Complexity and Formula Size Lower Bounds. After postdoctoral fellowships at the University of Orsay, Paris, Rutgers University, and Columbia University, he joined the Centre for Quantum Technologies as a Senior Research Fellow in 2010. In 2013 he was awarded a NRF fellowship and became an associate professor at Nanyang Technological University. In 2014 he became a Principal Investigator at CQT.


  • T. Lee, Z.H. Wei, Ronald de Wolf. Some upper and lower bounds on PSD-rank.
  • R. Jain, Nisheeth K. Vishnoi, T. Lee. A quadratically tight partition bound for classical communication complexity and query complexity.
  • Aleksandrs Belovs, T. Lee. Quantum Algorithm for k-distinctness with Prior Knowledge on the Input.
  • T. Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek. An adversary for algorithms.


  • D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs. (2017). Quadratically Tight Relations for Randomized Query Complexity. Electronic Colloquium on Computational Complexity 123
  • A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal. (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS 2017
  • A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee. (2017). Separating quantum communication and approximate rank. Proc. IEEE CCC
  • T. Lee, Frederic Magniez, M. Santha. (2017). Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing. Algorithmica 77 459-486
  • T. Lee, Z.H. Wei, Ronald de Wolf. (2017). Some upper and lower bounds on PSD-rank. Mathematical Programming 162 495--521
  • Gábor Braun, R. Jain, T. Lee, Sebastian Pokutta. (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 1-50
  • A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, R. Jain, Robin Kothari, T. Lee, M. Santha. (2016). Separations in communication complexity using cheat sheets and information complexity. Proc. IEEE FOCS 555-564
  • T. Lee, A.Prakash, R. de Wolf, H. Yuen. (2016). On the sum-of-squares degree of symmetric quadratic functions. Proc. IEEE CCC
  • T. Lee, N. Leonardos, M. Saks, F. Wang. (2016). Hellinger volume and number-on-the-forehead communication complexity. Journal of Computer and System Sciences
  • Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, T. Lee, M. Santha, Juris Smotrovs. (2016). Separation in query complexity based on pointer functions. Proceedings of ACM STOC 800-813
  • Friesen, Mirjam, Hamed, Aya, T. Lee, Theis, Dirk Oliver. (2015). Fooling-sets and rank. European Journal of Combinatorics 48
  • J. Kaniewski, T. Lee, de Wolf, Ronald. (2015). Query Complexity in Expectation. Automata, Languages, and Programming 9134
  • T. Lee, Frederic Magniez, M. Santha. (2015). Improved quantum query algorithms for Triangle Finding and Associativity Testing. Algorithmica 1486-1502
  • T. Lee, Jeremie Roland. (2012). A strong direct product theorem for quantum query complexity. IEEE Conference on Computational Complexity 27 236-246
  • G. Ivanyos, H. Klauck, T. Lee, M. Santha, Ronald de Wolf. (2012). New bounds on the classical and quantum communication complexity of some graph properties. Proceedings of FSTTCS 148-159
  • T. Lee, Frederic Magniez, M. Santha. (2012). Learning graph based quantum query algorithms for finding constant-size subgraphs. CJTCS 2012 1-21
  • Jop Briet, Harry Buhrman, T. Lee, Thomas Vidick. (2011). All Schatten spaces endowed with the Schur product are Q-algebras. Journal of Functional Analysis 262 1-9
  • T. Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, M. Szegedy. (2011). Quantum query complexity of state conversion. Proc. IEEE FOCS
  • T. Lee, S. Zhang. (2010). Composition theorems in communication complexity . Proceedings of ICALP
  • T. Lee, A. Shraibman. (2009). Disjointness is hard in the multi-party number-on-the-forehead model. Proc. IEEE CCC 309-336
  • T. Lee, R. Mittal. (2009). Product theorems via semidefinite programming.. Proceedings of ICALP 5125 674-685
  • T. Lee, A. Shraibman. (2009). An approximation algorithm for approximation rank. Proc. IEEE CCC 351-357
  • T. Lee, G. Schechtman,, A. Shraibman. (2009). Lower bounds on quantum multiparty communication complexity . Proc. IEEE CCC 254-262
  • T. Lee, A. Shraibman, R. Spalek. (2008). A direct product theorem for discrepancy. Proc. IEEE CCC 71-80
  • A.M. Childs, T. Lee. (2008). Optimal quantum adversary lower bounds for ordered search. . Proceedings of ICALP 5125 869-880
  • T. Lee. (2007). A new rank technique for formula size lower bounds. Proceedings of STACS 4393 145-156
  • P. Hoyer, T. Lee, R. Spalek. (2007). Negative weights make adversaries stronger. ACM STOC 526-535
  • T. Lee, A. Shraibman. (2007). Lower bounds on communication complexity . Foundations & Trends in Theoretical Computer Science 4 263-399
  • L. Fortnow, T. Lee, N. Vereshchagin. (2006). Kolmogorov Complexity with Error. Proceedings of ACM STOC 3884 137-148
  • S. Laplante, T. Lee, M. Szegedy. (2006). The quantum adversary method and formula size lower bounds . Proc. IEEE CCC 15 163-196
  • H. Buhrman, T. Lee, D. van Melkebeek. (2004). Language Compression and Pseudorandom Generators. Proc. IEEE CCC 14 228-255
  • T. Lee, A. Romashchenko. (2004). Resource Bounded Symmetry of Information Revisited . Theoretical Computer Science 345 386-405
  • T. Lee. (2003). Arithmetical Definability over Finite Structures. Mathematical Logic Quarterly 49 385-392
  • V. Tereshko, T. Lee. (2002). How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony . Open Sys. Info. Dyn. 9 1-13
  • Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, T. Lee, M. Santha, Juris Smotrovs. Separations in Query Complexity Based on Pointer Functions. JACM