TL
Troy Lee
quant-phcs.CCcs.DSmath.COmath.OCcs.DMcs.ITcs.LGmath.ITq-fin.GN
On Valency
published · living versionsW_bccjzcam·v1 · currentpublished
Preprints & journals
43 papers in the corpus · 2006–2026The quantum query complexity of the semigroup product problem2609.39974v1 · Troy Lee, Miklos Santha2026 · 0 citationsarXiv
On the quantum time complexity of divide and conquer2311.16401v1 · Jonathan Allcock, Jinge Bao, Aleksandrs Belovs et al.2023 · 2 citationsProceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), pp. 9:1-9:20, 2025
Cut query algorithms with star contraction2201.05674v1 · Simon Apers, Yuval Efron, PawełGawrychowski et al.2022 · 6 citationsarXiv
Finding the KT partition of a weighted graph in near-linear time2111.01378v1 · Simon Apers, PawełGawrychowski, Troy Lee2021 · 0 citationsarXiv
A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs2110.15587v2 · Simon Apers, Arinta Auza, Troy Lee2021 · 0 citationsarXiv
On the query complexity of connectivity with global queries2109.02115v1 · Arinta Auza, Troy Lee2021 · 2 citationsarXiv
Quantum complexity of minimum cut2011.09823v3 · Simon Apers, Troy Lee2020 · 2 citationsarXiv
On the cut dimension of a graph2011.05085v2 · Troy Lee, Tongyang Li, Miklos Santha et al.2020 · 6 citationsarXiv
Quantum algorithms for graph problems with cut queries2007.08285v2 · Troy Lee, Miklos Santha, Shengyu Zhang2020 · 13 citationsarXiv
The quantum query complexity of composition with a relation2004.06439v1 · Aleksandrs Belovs, Troy Lee2020 · 3 citationsarXiv
A composition theorem for randomized query complexity via max conflict complexity1811.10752v1 · Dmitry Gavinsky, Troy Lee, Miklos Santha et al.2018 · 4 citationsarXiv
Bounding quantum-classical separations for classes of nonlocal games1811.11068v1 · Tom Bannink, Jop Briet, Harry Buhrman et al.2018 · 3 citationsarXiv
Two new results about quantum exact learning1810.00481v4 · Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee et al.2018 · 9 citationsQuantum 5, 587 (2021)
Strategies for quantum races1809.03671v2 · Troy Lee, Maharshi Ray, Miklos Santha2018 · 10 citationsarXiv
On the randomised query complexity of composition1801.02226v1 · Dmytro Gavinsky, Troy Lee, Miklos Santha2018 · 5 citationsarXiv
Quantum attacks on Bitcoin, and how to protect against them1710.10377v1 · Divesh Aggarwal, Gavin K. Brennen, Troy Lee et al.2017 · 228 citationsLedger, [S.l.], v. 3, oct. 2018
Quadratically Tight Relations for Randomized Query Complexity1708.00822v1 · Dmitry Gavinsky, Rahul Jain, Hartmut Klauck et al.2017 · 1 citationarXiv
A Composition Theorem for Randomized Query Complexity1706.00335v2 · Anurag Anshu, Dmitry Gavinsky, Rahul Jain et al.2017 · 2 citationsarXiv
Separating quantum communication and approximate rank1611.05754v1 · Anurag Anshu, Shalev Ben-David, Ankit Garg et al.2016 · 3 citations32nd Conference on Computational Complexity (CCC 2017), Leibniz International Proceedings in Informatics (LIPIcs) 79, pp. 24:1-24:33 (2017)
Separations in communication complexity using cheat sheets and information complexity1605.01142v2 · Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David et al.2016 · 14 citationsProceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 555-564 (2016)
On the sum-of-squares degree of symmetric quadratic functions1601.02311v2 · Troy Lee, Anupam Prakash, Ronald de Wolf et al.2016 · 11 citationsarXiv
Separations in Query Complexity Based on Pointer Functions1506.04719v3 · Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs et al.2015 · 31 citationsarXiv
Query complexity in expectation1411.7280v1 · Jedrzej Kaniewski (CQT, QuTech, Delft) et al.2014 · 1 citationarXiv
The square root rank of the correlation polytope is exponential1411.6712v1 · Troy Lee, Zhaohui Wei2014 · 3 citationsarXiv
Hellinger volume and number-on-the-forehead communication complexity1407.5425v1 · Troy Lee, Nikos Leonardos, Michael Saks et al.2014 · 2 citationsarXiv
Some upper and lower bounds on PSD-rank1407.4308v1 · Troy Lee, Zhaohui Wei, Ronald de Wolf2014 · 25 citationsarXiv
Rank and fooling set size1310.7321v1 · Aya Hamed, Troy Lee2013 · 1 citationarXiv
Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices1305.4147v1 · LeRoy Beasely, Troy Lee, Hartmut Klauck et al.2013 · 1 citationarXiv
Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing1210.1014v1 · Troy Lee, Frederic Magniez, Miklos Santha2012 · 33 citationsarXiv
Fooling sets and rank1208.2920v3 · Mirjam Friesen, Aya Hamed, Troy Lee et al.2012 · 2 citationsarXiv
New bounds on the classical and quantum communication complexity of some graph properties1204.4596v1 · Gabor Ivanyos, Hartmut Klauck, Troy Lee et al.2012 · 11 citationsarXiv
Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix1203.3961v4 · Troy Lee, Dirk Oliver Theis2012 · 14 citationsarXiv
A learning graph based quantum query algorithm for finding constant-size subgraphs1109.5135v3 · Troy Lee, Frederic Magniez, Miklos Santha2011 · 21 citationsarXiv
Quantum Algorithm for k-distinctness with Prior Knowledge on the Input1108.3022v1 · Aleksandrs Belovs, Troy Lee2011 · 25 citationsarXiv
A strong direct product theorem for quantum query complexity1104.4468v3 · Troy Lee, J'er'emie Roland2011 · 6 citations27th IEEE Conference on Computational Complexity (CCC'12), pages 236-246, 2012
Quantum query complexity of state conversion1011.3020v2 · Troy Lee, Rajat Mittal, Ben W. Reichardt et al.2010 · 139 citationsProc. 52nd IEEE Symp. on Foundations of Computer Science (FOCS), 2011, pages 344-353
Composition theorems in communication complexity1003.1443v1 · Troy Lee, Shengyu Zhang2010 · 33 citationsarXiv
Multiplayer XOR games and quantum communication complexity with clique-wise entanglement0911.4007v1 · Jop Briet, Harry Buhrman, Troy Lee et al.2009 · 20 citationsarXiv
An approximation algorithm for approximation rank0809.2093v2 · Troy Lee, Adi Shraibman2008 · 31 citationsarXiv
Product theorems via semidefinite programming0803.4206v2 · Troy Lee, Rajat Mittal2008 · 5 citationsarXiv
Disjointness is hard in the multi-party number on the forehead model0712.4279v2 · Troy Lee, Adi Shraibman2007 · 41 citationsarXiv
Optimal quantum adversary lower bounds for ordered search0708.3396v1 · Andrew M. Childs, Troy Lee2007 · 17 citationsProc. 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Lecture Notes in Computer Science 5125, pp. 869-880
Negative weights make adversaries strongerquant-ph/0611054v2 · Peter Hoyer (U Calgary), Troy Lee (LRI), Robert Spalek2006 · 214 citationsProceedings of 39th Annual Symposium on Theory of Computing (STOC), San Diego, California, pp. 526-535, 2007
Career total: 124 works. 43 are in this corpus.
Profile built from the corpus for this byline.
Author records are still filling in while the Hub is in alpha. If this is your page, you'll be able to claim it soon. Spot a mistake? Tell us.