Troy Lee
Visiting Research Associate Professor
S15-04-05
cqttjl@nus.edu.sg
Miklos Santha

Preprints

  • Marco Tomamichel, Gavin K. Brennen, M. Santha, T. Lee, D. Aggarwal. Quantum attacks on Bitcoin, and how to protect against them.
  • 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.

Publications

  • D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs. (2017). Quadratically Tight Relations for Randomized Query Complexity. CSR
  • 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, 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