Publications (33)
Bounding quantum-classical separations for classes of nonlocal games
Tom Bannink, Jop Briët, Harry Buhrman +2
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5
New bounds on the classical and quantum communication complexity of some graph properties
Gabor Ivanyos, Hartmut Klauck, Troy Lee +2
A composition theorem for randomized query complexity via max conflict complexity
Dmitry Gavinsky, Troy Lee, Miklos Santha +1
Some upper and lower bounds on PSD-rank
Troy Lee, Zhaohui Wei, Ronald de Wolf
Optimal quantum adversary lower bounds for ordered search
Andrew M. Childs, Troy Lee
Product theorems via semidefinite programming
Troy Lee, Rajat Mittal
On the sum-of-squares degree of symmetric quadratic functions
Troy Lee, Anupam Prakash, Ronald de Wolf +1
A note on the sign degree of formulas
Troy Lee
Tight adversary bounds for composite functions
Peter Hoyer, Troy Lee, Robert Spalek
Multiplayer XOR games and quantum communication complexity with clique-wise entanglement
Jop Briet, Harry Buhrman, Troy Lee +1
The quantum adversary method and classical formula size lower bounds
Sophie Laplante, Troy Lee, Mario Szegedy
Strategies for quantum races
Troy Lee, Maharshi Ray, Miklos Santha
Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
Aleksandrs Belovs, Troy Lee
The square root rank of the correlation polytope is exponential
Troy Lee, Zhaohui Wei
Separating quantum communication and approximate rank
Anurag Anshu, Shalev Ben-David, Ankit Garg +3
Rank and fooling set size
Aya Hamed, Troy Lee
Negative weights make adversaries stronger
Peter Hoyer, Troy Lee, Robert Spalek
A strong direct product theorem for quantum query complexity
Troy Lee, Jérémie Roland
Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing
Troy Lee, Frederic Magniez, Miklos Santha
Hellinger volume and number-on-the-forehead communication complexity
Troy Lee, Nikos Leonardos, Michael Saks +1
A quadratically tight partition bound for classical communication complexity and query complexity
Rahul Jain, Troy Lee, Nisheeth K. Vishnoi
Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix
Troy Lee, Dirk Oliver Theis
Composition theorems in communication complexity
Troy Lee, Shengyu Zhang
Disjointness is hard in the multi-party number on the forehead model
Troy Lee, Adi Shraibman
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
A learning graph based quantum query algorithm for finding constant-size subgraphs
Troy Lee, Frederic Magniez, Miklos Santha
Separations in Query Complexity Based on Pointer Functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs +3
Fooling sets and rank
Mirjam Friesen, Aya Hamed, Troy Lee +1
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices
LeRoy Beasely, Troy Lee, Hartmut Klauck +1
Query complexity in expectation
Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt +2