Troy Lee
Preprints & Publications
Quantum algorithms for graph problems with cut queries
On the cut dimension of a graph
Strategies for quantum races
Bounding quantum-classical separations for classes of nonlocal games
Some upper and lower bounds on PSD-rank
Separating quantum communication and approximate rank
A Composition Theorem for Randomized Query Complexity
Quadratically Tight Relations for Randomized Query Complexity
Separations in Query Complexity Based on Pointer Functions
Separation in query complexity based on pointer functions
Hellinger volume and number-on-the-forehead communication complexity
On the sum-of-squares degree of symmetric quadratic functions
Separations in communication complexity using cheat sheets and information complexity
Information-theoretic approximations of the nonnegative rank
Improved quantum query algorithms for Triangle Finding and Associativity Testing
Query Complexity in Expectation
Fooling-sets and rank
Learning graph based quantum query algorithms for finding constant-size subgraphs
New bounds on the classical and quantum communication complexity of some graph properties
A strong direct product theorem for quantum query complexity
Quantum query complexity of state conversion
All Schatten spaces endowed with the Schur product are Q-algebras
Composition theorems in communication complexity
Lower bounds on quantum multiparty communication complexity
An approximation algorithm for approximation rank
Product theorems via semidefinite programming.
Disjointness is hard in the multi-party number-on-the-forehead model
Optimal quantum adversary lower bounds for ordered search.
A direct product theorem for discrepancy
Lower bounds on communication complexity
Negative weights make adversaries stronger
A new rank technique for formula size lower bounds
The quantum adversary method and formula size lower bounds
Kolmogorov Complexity with Error
Resource Bounded Symmetry of Information Revisited
Language Compression and Pseudorandom Generators
Arithmetical Definability over Finite Structures
How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony
An adversary for algorithms
Quantum Algorithm for k-distinctness with Prior Knowledge on the Input
A quadratically tight partition bound for classical communication complexity and query complexity
Two new results about quantum exact learning
The quantum query complexity of composition with a relation
