Troy Lee

ORCID

Publication Activity (10 Years)

Years Active: 2002-2023
Publications (10 Years): 44

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

STOC

Publications

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
On the quantum time complexity of divide and conquer. CoRR (2023)
Simon Apers, Pawel Gawrychowski, Troy Lee
Finding the KT Partition of a Weighted Graph in Near-Linear Time. APPROX/RANDOM (2022)
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut query algorithms with star contraction. CoRR (2022)
Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
Cut Query Algorithms with Star Contraction. FOCS (2022)
Simon Apers, Pawel Gawrychowski, Troy Lee
Finding the KT partition of a weighted graph in near-linear time. CoRR (2021)
Simon Apers, Troy Lee
Quantum Complexity of Minimum Cut. Computational Complexity Conference (2021)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
Two new results about quantum exact learning. Quantum 5 (2021)
Troy Lee, Miklos Santha, Shengyu Zhang
Quantum algorithms for graph problems with cut queries. SODA (2021)
Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang
On the Cut Dimension of a Graph. Computational Complexity Conference (2021)
Simon Apers, Arinta Auza, Troy Lee
A sublinear time quantum algorithm for s-t minimum cut on dense simple graphs. CoRR (2021)
Arinta Auza, Troy Lee
On the query complexity of connectivity with global queries. CoRR (2021)
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. Theory Comput. Syst. 64 (1) (2020)
Aleksandrs Belovs, Troy Lee
The quantum query complexity of composition with a relation. CoRR (2020)
Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang
On the cut dimension of a graph. CoRR (2020)
Troy Lee, Miklos Santha, Shengyu Zhang
Quantum algorithms for graph problems with cut queries. CoRR (2020)
Simon Apers, Troy Lee
Quantum query complexity of edge connectivity. CoRR (2020)
Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee
Bounding Quantum-Classical Separations for Classes of Nonlocal Games. STACS (2019)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
Two New Results About Quantum Exact Learning. ICALP (2019)
Troy Lee, Maharshi Ray, Miklos Santha
Strategies for Quantum Races. ITCS (2019)
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP (2019)
Dmitry Gavinsky, Troy Lee, Miklos Santha
On the randomised query complexity of composition. CoRR (2018)
Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. CSR (2018)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf
Two new results about quantum exact learning. CoRR (2018)
Troy Lee, Maharshi Ray, Miklos Santha
Strategies for quantum races. CoRR (2018)
Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
A composition theorem for randomized query complexity via max conflict complexity. CoRR (2018)
Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco Tomamichel
Quantum Attacks on Bitcoin, and How to Protect Against Them. Ledger 3 (2018)
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Troy Lee, Frédéric Magniez, Miklos Santha
Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. Algorithmica 77 (2) (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity. FSTTCS (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. 24 (2017)
Troy Lee, Zhaohui Wei, Ronald de Wolf
Some upper and lower bounds on PSD-rank. Math. Program. 162 (1-2) (2017)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. J. ACM 64 (5) (2017)
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
Quadratically Tight Relations for Randomized Query Complexity. CoRR (2017)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Separating Quantum Communication and Approximate Rank. Computational Complexity Conference (2017)
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
Information-theoretic approximations of the nonnegative rank. Comput. Complex. 26 (1) (2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
A Composition Theorem for Randomized Query Complexity. CoRR (2017)
Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen
On the sum-of-squares degree of symmetric quadratic functions. CoRR (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. 23 (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS (2016)
Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
Hellinger volume and number-on-the-forehead communication complexity. J. Comput. Syst. Sci. 82 (6) (2016)
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
Separations in communication complexity using cheat sheets and information complexity. CoRR (2016)
Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen
On the Sum-of-Squares Degree of Symmetric Quadratic Functions. Computational Complexity Conference (2016)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
Separating quantum communication and approximate rank. CoRR (2016)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in query complexity based on pointer functions. STOC (2016)
Hartmut Klauck, Troy Lee, Dirk Oliver Theis, Rekha R. Thomas
Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082). Dagstuhl Reports 5 (2) (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. 22 (2015)
Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
Query Complexity in Expectation. ICALP (1) (2015)
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
Separations in Query Complexity Based on Pointer Functions. CoRR (2015)
Mirjam Friesen, Aya Hamed, Troy Lee, Dirk Oliver Theis
Fooling-sets and rank. Eur. J. Comb. 48 (2015)
Rahul Jain, Troy Lee, Nisheeth K. Vishnoi
A quadratically tight partition bound for classical communication complexity and query complexity. CoRR (2014)
Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
Hellinger volume and number-on-the-forehead communication complexity. CoRR (2014)
Noga Alon, Troy Lee, Adi Shraibman
The Cover Number of a Matrix and its Algorithmic Applications. APPROX-RANDOM (2014)
Troy Lee, Zhaohui Wei, Ronald de Wolf
Some upper and lower bounds on PSD-rank. CoRR (2014)
Troy Lee, Zhaohui Wei
The square root rank of the correlation polytope is exponential. CoRR (2014)
Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
Query complexity in expectation. CoRR (2014)
LeRoy Beasely, Troy Lee, Hartmut Klauck, Dirk Oliver Theis
Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices CoRR (2013)
Troy Lee, Jérémie Roland
A strong direct product theorem for quantum query complexity. Comput. Complex. 22 (2) (2013)
Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick
Multipartite entanglement in XOR games. Quantum Inf. Comput. 13 (3-4) (2013)
LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theis
Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082). Dagstuhl Reports 3 (2) (2013)
Troy Lee, Adi Shraibman
Matrix Completion From any Given Set of Observations. NIPS (2013)
Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
Information-theoretic approximations of the nonnegative rank. Electron. Colloquium Comput. Complex. 20 (2013)
Troy Lee, Frédéric Magniez, Miklos Santha
Improved quantum query algorithms for triangle finding and associativity testing. SODA (2013)
Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala
The approximate rank of a matrix and its algorithmic applications: approximate rank. STOC (2013)
Aya Hamed, Troy Lee
Rank and fooling set size. CoRR (2013)
Troy Lee, Dirk Oliver Theis
Lower Bounds for Sizes of Semidefinite Formulations for Some Combinatorial Optimization Problems. CTW (2012)
Troy Lee, Dirk Oliver Theis
Lower bounds for sizes of semidefinite formulations for some combinatorial optimization problems CoRR (2012)
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
New bounds on the classical and quantum communication complexity of some graph properties CoRR (2012)
Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
New bounds on the classical and quantum communication complexity of some graph properties. FSTTCS (2012)
Troy Lee, Jérémie Roland
A Strong Direct Product Theorem for Quantum Query Complexity. Computational Complexity Conference (2012)
Troy Lee, Frédéric Magniez, Miklos Santha
Learning graph based quantum query algorithms for finding constant-size subgraphs. Chic. J. Theor. Comput. Sci. 2012 (2012)
Troy Lee, Jérémie Roland
A strong direct product theorem for quantum query complexity CoRR (2011)
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy
Quantum Query Complexity of State Conversion. FOCS (2011)
Troy Lee, Frédéric Magniez, Miklos Santha
A learning graph based quantum query algorithm for finding constant-size subgraphs CoRR (2011)
Troy Lee, Shengyu Zhang
Composition theorems in communication complexity CoRR (2010)
Troy Lee, Shengyu Zhang
Composition Theorems in Communication Complexity. ICALP (1) (2010)
Troy Lee, Gideon Schechtman, Adi Shraibman
Lower Bounds on Quantum Multiparty Communication Complexity. Computational Complexity Conference (2009)
Troy Lee, Adi Shraibman
An Approximation Algorithm for Approximation Rank. Computational Complexity Conference (2009)
Troy Lee
A note on the sign degree of formulas CoRR (2009)
Troy Lee, Adi Shraibman
Lower Bounds in Communication Complexity. Found. Trends Theor. Comput. Sci. 3 (4) (2009)
Troy Lee, Adi Shraibman
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. Comput. Complex. 18 (2) (2009)
Troy Lee, Rajat Mittal
Product theorems via semidefinite programming CoRR (2008)
Andrew M. Childs, Troy Lee
Optimal Quantum Adversary Lower Bounds for Ordered Search. ICALP (1) (2008)
Troy Lee, Adi Shraibman
Disjointness is hard in the multi-party number-on-the-forehead model. Electron. Colloquium Comput. Complex. 15 (003) (2008)
Troy Lee, Adi Shraibman
Approximation norms and duality for communication complexity lower bounds. Computational Complexity of Discrete Problems (2008)
Troy Lee, Adi Shraibman
An approximation algorithm for approximation rank CoRR (2008)
Troy Lee, Adi Shraibman, Robert Spalek
A Direct Product Theorem for Discrepancy. Computational Complexity Conference (2008)
Troy Lee, Rajat Mittal
Product Theorems Via Semidefinite Programming. ICALP (1) (2008)
Troy Lee, Adi Shraibman
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. Computational Complexity Conference (2008)
Troy Lee
A New Rank Technique for Formula Size Lower Bounds. STACS (2007)
Peter Høyer, Troy Lee, Robert Spalek
Negative weights make adversaries stronger. STOC (2007)
Troy Lee, Adi Shraibman
Disjointness is hard in the multi-party number on the forehead model CoRR (2007)
Sophie Laplante, Troy Lee, Mario Szegedy
The Quantum Adversary Method and Classical Formula Size Lower Bounds. Comput. Complex. 15 (2) (2006)
Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
Kolmogorov Complexity with Error. STACS (2006)
Troy Lee, Andrei E. Romashchenko
Resource bounded symmetry of information revisited. Theor. Comput. Sci. 345 (2-3) (2005)
Sophie Laplante, Troy Lee, Mario Szegedy
The Quantum Adversary Method and Classical Formula Size Lower Bounds. Computational Complexity Conference (2005)
Harry Buhrman, Troy Lee, Dieter van Melkebeek
Language compression and pseudorandom generators. Comput. Complex. 14 (3) (2005)
Troy Lee, Andrei E. Romashchenko
On Polynomially Time Bounded Symmetry of Information Electron. Colloquium Comput. Complex. (031) (2004)
Troy Lee, Dieter van Melkebeek, Harry Buhrman
Language Compression and Pseudorandom Generators Electron. Colloquium Comput. Complex. (002) (2004)
Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
Kolmogorov Complexity with Error Electron. Colloquium Comput. Complex. (080) (2004)
Harry Buhrman, Troy Lee, Dieter van Melkebeek
Language Compression and Pseudorandom Generators. Computational Complexity Conference (2004)

Troy Lee.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Troy Lee