Troy Lee
Preprints
- Aleksandrs Belovs, T. Lee, T. Lee. The quantum query complexity of composition with a relation.
- T. Lee, T. Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek. An adversary for algorithms.
- R. Jain, Nisheeth K. Vishnoi, T. Lee, T. Lee. A quadratically tight partition bound for classical communication complexity and query complexity.
- Aleksandrs Belovs, T. Lee, T. Lee. Quantum Algorithm for k-distinctness with Prior Knowledge on the Input.
- T. Lee, T. Lee, Z.H. Wei, Ronald de Wolf. Some upper and lower bounds on PSD-rank.
Publications
- D. Gavinsky, T. Lee, M. Santha, Swagato Sanyal, D. Gavinsky, T. Lee. (2022). A composition theorem for randomized query complexity via max conflict complexity. Theory of Computing 18
- T. Lee, Tongyang Li, M. Santha, Shengyu Zhang, T. Lee. (2021). On the cut dimension of a graph. Proceedings of the Computational Complexity Conference 200 15:1-15:35
- T. Lee, M. Santha, Shengyu Zhang, T. Lee. (2021). Quantum algorithms for graph problems with cut queries. ACM-SIAM Symposium on Discrete Algorithms (SODA) 939-958
- D. Gavinsky, R. Jain, T. Lee, M. Santha, Swagato Sanyal, Jevgenijs Vihrovs, D. Gavinsky, H. Klauck, S.Kundu, T. Lee. (2020). Quadratically Tight Relations for Randomized Query Complexity. Theory of Computing Systems 64 101-119
- Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, T. Lee, T. Lee. (2019). Bounding quantum-classical separations for classes of nonlocal games. Proceedings of STACS
- T. Lee, M. Santha, T. Lee, M.Ray. (2019). Strategies for quantum races. ITCS 14
- D. Aggarwal, Gavin K. Brennen, T. Lee, M. Santha, M. Tomamichel, T. Lee. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3
- D. Aggarwal, Gavin K. Brennen, T. Lee, M. Santha, M. Tomamichel, T. Lee. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger
- T. Lee, Juris Smotrovs, M. Santha, Kaspars Balodis, Andris Ambainis, Aleksandrs Belovs, T. Lee. (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64
- D. Gavinsky, D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs. (2017). Quadratically Tight Relations for Randomized Query Complexity. CSR
- A. Anshu, A. Anshu, D. Gavinsky, D. Gavinsky, R. Jain, S.Kundu, T. Lee, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal. (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS
- A. Anshu, A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee, T. Lee. (2017). Separating quantum communication and approximate rank. Proc. IEEE CCC
- T. Lee, T. Lee, Z.H. Wei, Ronald de Wolf. (2017). Some upper and lower bounds on PSD-rank. Mathematical Programming 162 495--521
- Gabor Braun, R. Jain, T. Lee, T. Lee, Sebastian Pokutta. (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 26 147–197
- A. Anshu, A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, R. Jain, Robin Kothari, T. Lee, T. Lee, M. Santha. (2016). Separations in communication complexity using cheat sheets and information complexity. Proc. IEEE FOCS 555-564
- T. Lee, 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, 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, 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, T. Lee, Theis, Dirk Oliver. (2015). Fooling-sets and rank. European Journal of Combinatorics 48
- J. Kaniewski, T. Lee, T. Lee, de Wolf, Ronald. (2015). Query Complexity in Expectation. Automata, Languages, and Programming 9134
- T. Lee, T. Lee, Frederic Magniez, M. Santha. (2015). Improved quantum query algorithms for Triangle Finding and Associativity Testing. Algorithmica 1486-1502
- T. Lee, 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, 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, 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, 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, T. Lee, Rajat Mittal, Ben Reichardt, Robert Spalek, M. Szegedy. (2011). Quantum query complexity of state conversion. Proc. IEEE FOCS
- T. Lee, T. Lee, S. Zhang. (2010). Composition theorems in communication complexity . Proceedings of ICALP
- T. Lee, T. Lee, A. Shraibman. (2009). Disjointness is hard in the multi-party number-on-the-forehead model. Proc. IEEE CCC 309-336
- T. Lee, T. Lee, R. Mittal. (2009). Product theorems via semidefinite programming.. Proceedings of ICALP 5125 674-685
- T. Lee, T. Lee, A. Shraibman. (2009). An approximation algorithm for approximation rank. Proc. IEEE CCC 351-357
- T. Lee, T. Lee, G. Schechtman,, A. Shraibman. (2009). Lower bounds on quantum multiparty communication complexity . Proc. IEEE CCC 254-262
- T. Lee, T. Lee, A. Shraibman, R. Spalek. (2008). A direct product theorem for discrepancy. Proc. IEEE CCC 71-80
- A.M. Childs, T. Lee, T. Lee. (2008). Optimal quantum adversary lower bounds for ordered search. . Proceedings of ICALP 5125 869-880
- T. Lee, T. Lee. (2007). A new rank technique for formula size lower bounds. Proceedings of STACS 4393 145-156
- P. Hoyer, T. Lee, T. Lee, R. Spalek. (2007). Negative weights make adversaries stronger. ACM STOC 526-535
- T. Lee, T. Lee, A. Shraibman. (2007). Lower bounds on communication complexity . Foundations & Trends in Theoretical Computer Science 4 263-399
- L. Fortnow, T. Lee, T. Lee, N. Vereshchagin. (2006). Kolmogorov Complexity with Error. Proceedings of ACM STOC 3884 137-148
- S. Laplante, T. Lee, T. Lee, M. Szegedy. (2006). The quantum adversary method and formula size lower bounds . Proc. IEEE CCC 15 163-196
- H. Buhrman, T. Lee, T. Lee, D. van Melkebeek. (2004). Language Compression and Pseudorandom Generators. Proc. IEEE CCC 14 228-255
- T. Lee, T. Lee, A. Romashchenko. (2004). Resource Bounded Symmetry of Information Revisited . Theoretical Computer Science 345 386-405
- T. Lee, T. Lee. (2003). Arithmetical Definability over Finite Structures. Mathematical Logic Quarterly 49 385-392
- V. Tereshko, T. Lee, T. Lee. (2002). How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony . Open Sys. Info. Dyn. 9 1-13
- Srinivasan Arunachalam, Sourav Chakraborty, T. Lee, Manaswi Paraashar, Ronald de Wolf, T. Lee. Two new results about quantum exact learning. Proceedings of ICALP
