Troy Lee
Preprints
- T. Lee, T. Lee, Aleksandrs Belovs. 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
- T. Lee, Swagato Sanyal, M. Santha, T. Lee, D. Gavinsky. (2022). A composition theorem for randomized query complexity via max conflict complexity. Theory of Computing 18
- Shengyu Zhang, M. Santha, Tongyang Li, T. Lee, T. Lee. (2021). On the cut dimension of a graph. Proceedings of the Computational Complexity Conference 200 15:1-15:35
- T. Lee, Shengyu Zhang, M. Santha, T. Lee. (2021). Quantum algorithms for graph problems with cut queries. ACM-SIAM Symposium on Discrete Algorithms (SODA) 939-958
- Swagato Sanyal, M. Santha, T. Lee, R. Jain, H. Klauck, D. Gavinsky, T. Lee, S.Kundu, Jevgenijs Vihrovs. (2020). Quadratically Tight Relations for Randomized Query Complexity. Theory of Computing Systems 64 101-119
- Farrokh Labib, Harry Buhrman, Jop Briët, Tom Bannink, T. Lee, T. Lee. (2019). Bounding quantum-classical separations for classes of nonlocal games. Proceedings of STACS
- M.Ray, T. Lee, M. Santha, T. Lee. (2019). Strategies for quantum races. ITCS 14
- M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, T. Lee, M. Tomamichel. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger 3
- M. Santha, T. Lee, Gavin K. Brennen, D. Aggarwal, T. Lee, M. Tomamichel. (2018). Quantum attacks on Bitcoin, and how to protect against them. Ledger
- Kaspars Balodis, M. Santha, Juris Smotrovs, T. Lee, T. Lee, Aleksandrs Belovs, Andris Ambainis. (2017). Separations in Query Complexity Based on Pointer Functions. JACM 64
- 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, 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
- Manaswi Paraashar, T. Lee, Sourav Chakraborty, Srinivasan Arunachalam, T. Lee, Ronald de Wolf. Two new results about quantum exact learning. Proceedings of ICALP
