Troy Lee

According to our database, Troy Lee authored at least 69 papers between 2002 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

Optimal Composition Theorem for Randomized Query Complexity.

Dmytro Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Theory Comput., 2023

On the quantum time complexity of divide and conquer.

Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

CoRR, 2023

2022

Cut Query Algorithms with Star Contraction.

Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Finding the KT Partition of a Weighted Graph in Near-Linear Time.

Simon Apers, Pawel Gawrychowski, Troy Lee

Proceedings of the Approximation, 2022

Query Complexity

Mario Szegedy, Ilan Newman, Troy Lee

WorldScientific, ISBN: 9789813223226, 2022

2021

Two new results about quantum exact learning.

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf

Quantum, 2021

A sublinear time quantum algorithm for s-t minimum cut on dense simple graphs.

Simon Apers, Arinta Auza, Troy Lee

CoRR, 2021

On the query complexity of connectivity with global queries.

Arinta Auza, Troy Lee

CoRR, 2021

Quantum algorithms for graph problems with cut queries.

Troy Lee, Miklos Santha, Shengyu Zhang

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

On the Cut Dimension of a Graph.

Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang

Proceedings of the 36th Computational Complexity Conference, 2021

Quantum Complexity of Minimum Cut.

Simon Apers, Troy Lee

Proceedings of the 36th Computational Complexity Conference, 2021

2020

Quadratically Tight Relations for Randomized Query Complexity.

Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Theory Comput. Syst., 2020

Quantum query complexity of edge connectivity.

Simon Apers, Troy Lee

CoRR, 2020

The quantum query complexity of composition with a relation.

Aleksandrs Belovs, Troy Lee

CoRR, 2020

2019

Bounding Quantum-Classical Separations for Classes of Nonlocal Games.

Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Strategies for Quantum Races.

Troy Lee, Maharshi Ray, Miklos Santha

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity.

Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Quantum Attacks on Bitcoin, and How to Protect Against Them.

Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco Tomamichel

Ledger, 2018

Two new results about quantum exact learning.

Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf

CoRR, 2018

On the randomised query complexity of composition.

Dmitry Gavinsky, Troy Lee, Miklos Santha

CoRR, 2018

2017

Some upper and lower bounds on PSD-rank.

Troy Lee, Zhaohui Wei, Ronald de Wolf

Math. Program., 2017

Quadratically Tight Relations for Randomized Query Complexity.

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Electron. Colloquium Comput. Complex., 2017

A Composition Theorem for Randomized Query complexity.

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Electron. Colloquium Comput. Complex., 2017

Information-theoretic approximations of the nonnegative rank.

Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Comput. Complex., 2017

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing.

Troy Lee, Frédéric Magniez, Miklos Santha

Algorithmica, 2017

Separating Quantum Communication and Approximate Rank.

Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Hellinger volume and number-on-the-forehead communication complexity.

Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang

J. Comput. Syst. Sci., 2016

Separations in communication complexity using cheat sheets and information complexity.

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

Electron. Colloquium Comput. Complex., 2016

On the Sum-of-Squares Degree of Symmetric Quadratic Functions.

Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Fooling-sets and rank.

Mirjam Friesen, Aya Hamed, Troy Lee, Dirk Oliver Theis

Eur. J. Comb., 2015

Separations in Query Complexity Based on Pointer Functions.

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

Electron. Colloquium Comput. Complex., 2015

Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082).

Hartmut Klauck, Troy Lee, Dirk Oliver Theis, Rekha R. Thomas

Dagstuhl Reports, 2015

Query Complexity in Expectation.

Jedrzej Kaniewski, Troy Lee, Ronald de Wolf

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014

The square root rank of the correlation polytope is exponential.

Troy Lee, Zhaohui Wei

CoRR, 2014

A quadratically tight partition bound for classical communication complexity and query complexity.

Rahul Jain, Troy Lee, Nisheeth K. Vishnoi

CoRR, 2014

The Cover Number of a Matrix and its Algorithmic Applications.

Noga Alon, Troy Lee, Adi Shraibman

Proceedings of the Approximation, 2014

2013

Multipartite entanglement in XOR games.

Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick

Quantum Inf. Comput., 2013

Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082).

LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theis

Dagstuhl Reports, 2013

Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices

LeRoy Beasely, Troy Lee, Hartmut Klauck, Dirk Oliver Theis

CoRR, 2013

Rank and fooling set size.

Aya Hamed, Troy Lee

CoRR, 2013

A strong direct product theorem for quantum query complexity.

Troy Lee, Jérémie Roland

Comput. Complex., 2013

The approximate rank of a matrix and its algorithmic applications: approximate rank.

Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala

Proceedings of the Symposium on Theory of Computing Conference, 2013

Improved quantum query algorithms for triangle finding and associativity testing.

Troy Lee, Frédéric Magniez, Miklos Santha

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Matrix Completion From any Given Set of Observations.

Troy Lee, Adi Shraibman

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

2012

Learning graph based quantum query algorithms for finding constant-size subgraphs.

Troy Lee, Frédéric Magniez, Miklos Santha

Chic. J. Theor. Comput. Sci., 2012

New bounds on the classical and quantum communication complexity of some graph properties.

Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Lower Bounds for Sizes of Semidefinite Formulations for Some Combinatorial Optimization Problems.

Troy Lee, Dirk Oliver Theis

Proceedings of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2012

2011

A learning graph based quantum query algorithm for finding constant-size subgraphs

Troy Lee, Frédéric Magniez, Miklos Santha

CoRR, 2011

Quantum Query Complexity of State Conversion.

Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Composition Theorems in Communication Complexity.

Troy Lee, Shengyu Zhang

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Lower Bounds in Communication Complexity.

Troy Lee, Adi Shraibman

Found. Trends Theor. Comput. Sci., 2009

A note on the sign degree of formulas

Troy Lee

CoRR, 2009

Disjointness is Hard in the Multiparty Number-on-the-Forehead Model.

Troy Lee, Adi Shraibman

Comput. Complex., 2009

Lower Bounds on Quantum Multiparty Communication Complexity.

Troy Lee, Gideon Schechtman, Adi Shraibman

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

An Approximation Algorithm for Approximation Rank.

Troy Lee, Adi Shraibman

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Disjointness is hard in the multi-party number-on-the-forehead model.

Troy Lee, Adi Shraibman

Electron. Colloquium Comput. Complex., 2008

Product Theorems Via Semidefinite Programming.

Troy Lee, Rajat Mittal

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Optimal Quantum Adversary Lower Bounds for Ordered Search.

Andrew M. Childs, Troy Lee

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Approximation norms and duality for communication complexity lower bounds.

Troy Lee, Adi Shraibman

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

A Direct Product Theorem for Discrepancy.

Troy Lee, Adi Shraibman, Robert Spalek

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Negative weights make adversaries stronger.

Peter Høyer, Troy Lee, Robert Spalek

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

A New Rank Technique for Formula Size Lower Bounds.

Troy Lee

Proceedings of the STACS 2007, 2007

2006

The Quantum Adversary Method and Classical Formula Size Lower Bounds.

Sophie Laplante, Troy Lee, Mario Szegedy

Comput. Complex., 2006

2005

Resource bounded symmetry of information revisited.

Troy Lee, Andrei E. Romashchenko

Theor. Comput. Sci., 2005

Language compression and pseudorandom generators.

Harry Buhrman, Troy Lee, Dieter van Melkebeek

Comput. Complex., 2005

2004

Kolmogorov Complexity with Error

Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 2004

On Polynomially Time Bounded Symmetry of Information

Troy Lee, Andrei E. Romashchenko

Electron. Colloquium Comput. Complex., 2004

2003

Arithmetical definability over finite structures.

Troy Lee

Math. Log. Q., 2003

2002

How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony.

Valery Tereshko, Troy Lee

Open Syst. Inf. Dyn., 2002