#### Can supervise: YES

#### Publications

Ambainis, A, Balodis, K, Belovs, A, Lee, T, Santha, M & Smotrovs, J 2017, 'Separations in query complexity based on pointer functions', *Journal of the ACM*, vol. 64, no. 5.View/Download from: Publisher's site

#### View description

© 2017 ACM. In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total Boolean function is given by the function f on n = 2k bits defined by a complete binary tree of NAND gates of depth k, which achieves R0 ( f ) = O(D( f )0.7537).We show that this is false by giving an example of a total Boolean function f on n bits whose deterministic query complexity is Ω(n) while its zero-error randomized query complexity is O( √ n).We further show that the quantum query complexity of the same function is O(n1/4), giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities. We also construct a total Boolean function g on n variables that has zero-error randomized query complexity Ω(n/ log(n)) and bounded-error randomized query complexity R(g) = O( √ n). This is the first superlinear separation between these two complexity measures. The exact quantum query complexity of the same function is QE (g) = O( √ n). These functions show that the relations D( f ) = O(R1 (f)2) and R0 ( f ) = O(R(f)2) are optimal, up to polylogarithmic factors. Further variations of these functions give additional separations between other query complexity measures: A cubic separation between Q and R0, a 3/2-power separation between QE and R, and a 4th-power separation between approximate degree and bounded-error randomized query complexity. All of these examples are variants of a function recently introduced by Goos, Pitassi, and Watson, which they used to separate the unambiguous 1-certificate complexity from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.

Lee, T, Magniez, F & Santha, M 2017, 'Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing', *Algorithmica*, vol. 77, no. 2, pp. 459-486.View/Download from: Publisher's site

#### View description

© 2015, Springer Science+Business Media New York. We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9 / 7). This improves the previous best algorithm of Belovs (Proceedings of 44th symposium on theory of computing conference, pp 77–84, 2012) making O(n35 / 27) queries. For the problem of determining if an operation ∘ : S× S→ S is associative, we give an algorithm making O(| S| 10 / 7) queries, the first improvement to the trivial O(| S| 3 / 2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm.

Lee, T, Prakash, A, De Wolf, R & Yuen, H 2016, 'On the sum-of-squares degree of symmetric quadratic functions', *Leibniz International Proceedings in Informatics, LIPIcs*, vol. 50, p. 17:1-17:31.View/Download from: Publisher's site

#### View description

© Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. We study how well functions over the boolean hypercube of the form fk(x) = (|x|-k)(|x|-k-1) can be approximated by sums of squares of low-degree polynomials, obtaining good bounds for the case of approximation in '1-norm as well as in '1-norm. We describe three complexity-theoretic applications: (1) a proof that the recent breakthrough lower bound of Lee, Raghavendra, and Steurer [19] on the positive semidefinite extension complexity of the correlation and TSP polytopes cannot be improved further by showing better sum-of-squares degree lower bounds on '1-approximation of fk; (2) a proof that Grigoriev's lower bound on the degree of Positivstellensatz refutations for the knapsack problem is optimal, answering an open question from [12]; (3) bounds on the query complexity of quantum algorithms whose expected output approximates such functions.

Lee, T, Mittal, R, Reichardt, BW, Špalek, R & Szegedy, M 2011, 'Quantum query complexity of state conversion', *Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS*, pp. 344-353.View/Download from: Publisher's site

#### View description

State conversion generalizes query complexity to the problem of converting between two input-dependent quantum states by making queries to the input. We characterize the complexity of this problem by introducing a natural information-theoretic norm that extends the Schur product operator norm. The complexity of converting between two systems of states is given by the distance between them, as measured by this norm. In the special case of function evaluation, the norm is closely related to the general adversary bound, a semi-definite program that lower-bounds the number of input queries needed by a quantum algorithm to evaluate a function. We thus obtain that the general adversary bound characterizes the quantum query complexity of any function whatsoever. This generalizes and simplifies the proof of the same result in the case of boolean input and output. Also in the case of function evaluation, we show that our norm satisfies a remarkable composition property, implying that the quantum query complexity of the composition of two functions is at most the product of the query complexities of the functions, up to a constant. Finally, our result implies that discrete and continuous-time query models are equivalent in the bounded-error setting, even for the general state-conversion problem. © 2011 IEEE.

Lee, T & Shraibman, A 2009, 'An approximation algorithm for approximation rank', *Proceedings of the Annual IEEE Conference on Computational Complexity*, pp. 351-357.View/Download from: Publisher's site

#### View description

One of the strongest techniques available for showing lower bounds on bounded-error communication complexity is the logarithm of the approximation rank of the communication matrix-the minimum rank of a matrix which is close to the communication matrix in ℓ ∞ norm. Krause showed that the logarithm of approximation rank is a lower bound in the randomized case, and later Buhrman and de Wolf showed it could also be used for quantum communication complexity. As a lower bound technique, approximation rank has two main drawbacks: it is difficult to compute, and it is not known to lower bound the model of quantum communication complexity with entanglement. Linial and Shraibman recently introduced a quantity, called Υ α2, to quantum communication complexity, showing that it can be used to lower bound communication in the model with shared entanglement. Here α is a measure of approximation which is related to the allowable error probability of the protocol. This quantity can be written as a semidefinite program and gives bounds at least as large as many techniques in the literature, although it is smaller than the corresponding α-approximation rank, rkα. We show that in fact log Υ α2 (A) and log rkα (A) agree up to small factors. As corollaries we obtain a constant factor polynomial time approximation algorithm to the logarithm of approximation rank, and that the logarithm of approximation rank is a lower bound for quantum communication complexity with entanglement. © 2009 IEEE.

Lee, T & Mittal, R 2008, 'Product theorems via semidefinite programming', *Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*, vol. 5125 LNCS, no. PART 1, pp. 674-685.View/Download from: Publisher's site

#### View description

The tendency of semidefinite programs to compose perfectly under product has been exploited many times in complexity theory: for example, by Lovász to determine the Shannon capacity of the pentagon; to show a direct sum theorem for non-deterministic communication complexity and direct product theorems for discrepancy; and in interactive proof systems to show parallel repetition theorems for restricted classes of games. Despite all these examples of product theorems-some going back nearly thirty years-it was only recently that Mittal and Szegedy began to develop a general theory to explain when and why semidefinite programs behave perfectly under product. This theory captured many examples in the literature, but there were also some notable exceptions which it could not explain-namely, an early parallel repetition result of Feige and Lovász, and a direct product theorem for the discrepancy method of communication complexity by Lee, Shraibman, and Špalek. We extend the theory of Mittal and Szegedy to explain these cases as well. Indeed, to the best of our knowledge, our theory captures all examples of semidefinite product theorems in the literature. © 2008 Springer-Verlag.

Lee, T & Shraibman, A 2008, 'Disjointness is hard in the multi-party number-on-the-forehead model', *Proceedings of the Annual IEEE Conference on Computational Complexity*, pp. 81-91.View/Download from: Publisher's site

#### View description

We show that disjointness requires randomized communication Ω (n 1/(k+1)/22k) in the general k-party number-onthe-forehead model of complexity. The previous best lower bound was Ω (log n/k-1) • By results of Beanie, Pitassi, and Segerlind, this implies 2 nω(1) lower bounds on the size of tree-like Lovász-Schrijver proof systems needed to refute certain unsatisfiable CNFs, and super-polynomial lower bounds on the size of a broad class of tree-like proof systems whose terms are degree-d polynomial inequalities for d = log log n - O(log log log n). To prove our bound, we develop a new technique for showing lower bounds in the number-on-the-forehead model which is based on the norm induced by cylinder intersections. This bound naturally extends the linear program bound for rank useful in the two-party case to the case of more than two parties, where the fundamental concept of monochromatic rectangles is replaced by monochromatic cylinder intersections. Previously, the only general method known for showing lower bounds in the unrestricted number-on-the-forehead model was the discrepancy method, which is limited to bounds of size O(logn) for disjointness. To analyze the bound given by our new technique for the disjointness function, we build on an elegant framework developed by Sherstov in the two-party case and Chattopadhyay in the multi-party case which relates polynomial degree to communication complexity. Using this framework we are able to obtain bounds for any tensor of the form F(x1,..., Xk) = f{x1 ∧... ∧ Xk) where f is a function which only depends on the number of ones in the input. © 2008 IEEE.

Belovs, A & Lee, T, 'The quantum query complexity of composition with a relation'.

#### View description

The negative weight adversary method, $\mathrm{ADV}^\pm(g)$, is known to

characterize the bounded-error quantum query complexity of any Boolean function

$g$, and also obeys a perfect composition theorem $\mathrm{ADV}^\pm(f \circ

g^n) = \mathrm{ADV}^\pm(f) \mathrm{ADV}^\pm(g)$. Belovs gave a modified version

of the negative weight adversary method, $\mathrm{ADV}_{rel}^\pm(f)$, that

characterizes the bounded-error quantum query complexity of a relation $f

\subseteq \{0,1\}^n \times [K]$, provided the relation is efficiently

verifiable. A relation is efficiently verifiable if $\mathrm{ADV}^\pm(f_a) =

o(\mathrm{ADV}_{rel}^\pm(f))$ for every $a \in [K]$, where $f_a$ is the Boolean

function defined as $f_a(x) = 1$ if and only if $(x,a) \in f$. In this note we

show a perfect composition theorem for the composition of a relation $f$ with a

Boolean function $g$ \[ \mathrm{ADV}_{rel}^\pm(f \circ g^n) =

\mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) \enspace . \] For an efficiently

verifiable relation $f$ this means $Q(f \circ g^n) = \Theta(

\mathrm{ADV}_{rel}^\pm(f) \mathrm{ADV}^\pm(g) )$.

Hamed, A & Lee, T, 'Rank and fooling set size'.

#### View description

Say that A is a Hadamard factorization of the identity I_n of size n if the

entrywise product of A and the transpose of A is I_n. It can be easily seen

that the rank of any Hadamard factorization of the identity must be at least

sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be

achieved, and showed a boolean Hadamard factorization of the identity of rank

n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard

factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen

and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard

factorization of the identity A of size r(r-1)+1 and rank r over F_p.

Here we resolve the question for fields of zero characteristic, up to a

constant factor, giving a construction of Hadamard factorizations of the

identity of rank r and size (r+1)r/2. The matrices in our construction are

blockwise Toeplitz, and have entries whose magnitudes are binomial

coefficients.

Lee, T, 'A note on the sign degree of formulas'.

#### View description

Recent breakthroughs in quantum query complexity have shown that any formula

of size n can be evaluated with O(sqrt(n)log(n)/log log(n)) many quantum

queries in the bounded-error setting [FGG08, ACRSZ07, RS08b, Rei09]. In

particular, this gives an upper bound on the approximate polynomial degree of

formulas of the same magnitude, as approximate polynomial degree is a lower

bound on quantum query complexity [BBCMW01].

These results essentially answer in the affirmative a conjecture of O'Donnell

and Servedio [O'DS03] that the sign degree--the minimal degree of a polynomial

that agrees in sign with a function on the Boolean cube--of every formula of

size n is O(sqrt(n)).

In this note, we show that sign degree is super-multiplicative under function

composition. Combining this result with the above mentioned upper bounds on the

quantum query complexity of formulas allows the removal of logarithmic factors

to show that the sign degree of every size n formula is at most sqrt(n).

Lee, T, Santha, M & Zhang, S, 'Quantum algorithms for graph problems with cut queries'.

#### View description

Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of

vertices, a cut query on $G$ returns the number of edges of $G$ that have

exactly one endpoint in $S$. We show that there is a bounded-error quantum

algorithm that determines all connected components of $G$ after making

$O(\log(n)^6)$ many cut queries. In contrast, it follows from results in

communication complexity that any randomized algorithm even just to decide

whether the graph is connected or not must make at least $\Omega(n/\log(n))$

many cut queries. We further show that with $O(\log(n)^8)$ many cut queries a

quantum algorithm can with high probability output a spanning forest for $G$.

En route to proving these results, we design quantum algorithms for learning

a graph using cut queries. We show that a quantum algorithm can learn a graph

with maximum degree $d$ after $O(d \log(n)^2)$ many cut queries, and can learn

a general graph with $O(\sqrt{m} \log(n)^{3/2})$ many cut queries. These two

upper bounds are tight up to the poly-logarithmic factors, and compare to

$\Omega(dn)$ and $\Omega(m/\log(n))$ lower bounds on the number of cut queries

needed by a randomized algorithm for the same problems, respectively.

The key ingredients in our results are the Bernstein-Vazirani algorithm,

approximate counting with "OR queries", and learning sparse vectors from inner

products as in compressed sensing.

Arunachalam, S, Chakraborty, S, Lee, T, Paraashar, M & Wolf, RD 2019, 'Two new results about exact quantum learning', International Colloquium on Automata, Languages, and Programming, Greece.View/Download from: Publisher's site

Bannink, T, Briet, J, Buhrman, H, Lee, T & Labib, F 2019, 'Bounding quantum-classical separations for classes of nonlocal games', Symposium on Theoretical Aspects of Computer Science, Germany.

Gavinsky, D, Lee, T, Santha, M & Sanyal, S 2019, 'A composition theorem for randomized query complexity via max-conflict complexity', *Leibniz International Proceedings in Informatic*, International Colloquium on Automata, Languages, and Programming, Dagstuhl Publishing, Greece, pp. 1-13.View/Download from: Publisher's site

#### View description

For any relation f subseteq {0,1}^n x S and any partial Boolean function g:{0,1}^m -> {0,1,*}, we show that R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * sqrt{R_{1/3}(g)}) , where R_epsilon(*) stands for the bounded-error randomized query complexity with error at most epsilon, and f o g^n subseteq ({0,1}^m)^n x S denotes the composition of f with n instances of g. The new composition theorem is optimal, at least, for the general case of relational problems: A relation f_0 and a partial Boolean function g_0 are constructed, such that R_{4/9}(f_0) in Theta(sqrt n), R_{1/3}(g_0)in Theta(n) and R_{1/3}(f_0 o g_0^n) in Theta(n). The theorem is proved via introducing a new complexity measure, max-conflict complexity, denoted by bar{chi}(*). Its investigation shows that bar{chi}(g) in Omega(sqrt{R_{1/3}(g)}) for any partial Boolean function g and R_{1/3}(f o g^n) in Omega(R_{4/9}(f) * bar{chi}(g)) for any relation f, which readily implies the composition statement. It is further shown that bar{chi}(g) is always at least as large as the sabotage complexity of g.

Lee, T, Bannink, T, Briët, J, Buhrman, H & Labib, F 2019, 'Bounding Quantum-Classical Separations for Classes of Nonlocal Games', *LIPIcs : Leibniz International Proceedings in Informatics*, International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik, Berlin, Germany, pp. 1-11.View/Download from: Publisher's site

#### View description

We bound separations between the entangled and classical values for several classes of nonlocal t-player games. Our motivating question is whether there is a family of t-player XOR games for which the entangled bias is 1 but for which the classical bias goes down to 0, for fixed t. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-m games and show that their classical value is always at least 1/m + (m-1)/m t^{1-t}. Secondly, for free XOR games, in which the input distribution is of product form, we show beta(G) >= beta^*(G)^{2^t} where beta(G) and beta^*(G) are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is 1-epsilon then the classical value is at least 1-O(sqrt{epsilon log k}) where k is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.

Lee, T, Ray, M & Santha, M 2019, 'Strategies for quantum races', *10th Innovations in Theoretical Computer Science*, Innovations in Theoretical Computer Science, Schloss Dagstuhl, UCSD.View/Download from: Publisher's site

#### View description

We initiate the study of quantum races, games where two or more quantum computers compete to solve a computational problem. While the problem of dueling algorithms has been studied for classical deterministic algorithms [12], the quantum case presents additional sources of uncertainty for the players. The foremost among these is that players do not know if they have solved the problem until they measure their quantum state. This question of "when to measure?" presents a very interesting strategic problem. We develop a game-theoretic model of a multiplayer quantum race, and find an approximate Nash equilibrium where all players play the same strategy. In the two-party case, we further show that this strategy is nearly optimal in terms of payoff among all symmetric Nash equilibria. A key role in our analysis of quantum races is played by a more tractable version of the game where there is no payout on a tie; for such races we completely characterize the Nash equilibria in the two-party case. One application of our results is to the stability of the Bitcoin protocol when mining is done by quantum computers. Bitcoin mining is a race to solve a computational search problem, with the winner gaining the right to create a new block. Our results inform the strategies that eventual quantum miners should use, and also indicate that the collision probability – the probability that two miners find a new block at the same time – would not be too high in the case of quantum miners. Such collisions are undesirable as they lead to forking of the Bitcoin blockchain.

Lee, T & Roland, J 2012, 'A Strong Direct Product Theorem for Quantum Query Complexity', *2012 IEEE 27th Conference on Computational Complexity*, 2012 IEEE Conference on Computational Complexity (CCC), IEEE, Porto, Portugal.View/Download from: Publisher's site

Childs, AM & Lee, T 2008, 'Optimal Quantum Adversary Lower Bounds for Ordered Search', International Colloquium on Automata, Languages, and Programming, Springer Berlin Heidelberg, Reykjavik, Iceland, pp. 869-880.View/Download from: Publisher's site

Bannink, T, Briët, J, Buhrman, H, Labib, F & Lee, T 2019, 'Bounding quantum-classical separations for classes of nonlocal games'.

#### View description

© Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee. We bound separations between the entangled and classical values for several classes of nonlocal t-player games. Our motivating question is whether there is a family of t-player XOR games for which the entangled bias is 1 but for which the classical bias goes down to 0, for fixed t. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-m games and show that their classical value is always at least m1 + mm−1 t1−t. Secondly, for free XOR games, in which the input distribution is of product form, we show β(G) ≥ β∗(G)2t where β(G) and β∗(G) are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is 1 − then the classical value is at least 1 − O( log k) where k is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.

Lee, T & Zhang, S 2010, 'Composition theorems in communication complexity'.

#### View description

A well-studied class of functions in communication complexity are composed functions of the form (f g n ) (x,y)=f(g(x 1, y 1), ..., g(x n ,y n )). This is a rich family of functions which encompasses many of the important examples in the literature. It is thus of great interest to understand what properties of f and g affect the communication complexity of (f g n ), and in what way. Recently, Sherstov [She09] and independently Shi-Zhu [SZ09b] developed conditions on the inner function g which imply that the quantum communication complexity of f g n is at least the approximate polynomial degree of f. We generalize both of these frameworks. We show that the pattern matrix framework of Sherstov works whenever the inner function g is strongly balanced-we say that g: X ×Y →{-1,+1} is strongly balanced if all rows and columns in the matrix M g =[g(x,y)] x,y sum to zero. This result strictly generalizes the pattern matrix framework of Sherstov [She09], which has been a very useful idea in a variety of settings [She08b, RS08, Cha07, LS09a, CA08, BHN09]. Shi-Zhu require that the inner function g has small spectral discrepancy, a somewhat awkward condition to verify. We relax this to the usual notion of discrepancy. We also enhance the framework of composed functions studied so far by considering functions F(x,y)=f(g(x,y)), where the range of g is a group G. When G is Abelian, the analogue of the strongly balanced condition becomes a simple group invariance property of g. We are able to formulate a general lower bound on F whenever g satisfies this property. © 2010 Springer-Verlag Berlin Heidelberg.

Briet, J, Buhrman, H, Lee, T & Vidick, T, 'Multiplayer XOR games and quantum communication complexity with clique-wise entanglement'.

#### View description

XOR games are a simple computational model with connections to many areas of

complexity theory. Perhaps the earliest use of XOR games was in the study of

quantum correlations. XOR games also have an interesting connection to

Grothendieck's inequality, a fundamental theorem of analysis, which shows that

two players sharing entanglement can achieve at most a constant factor

advantage over players following classical strategies in an XOR game.

Perez-Garcia et al. show that when the players share GHZ states, this

advantage is bounded by a constant. We use a multilinear generalization of

Grothendieck's inequality due to Blei and Tonge to simplify the proof of the

second result and extend it to the case of so-called Schmidt states, answering

an open problem of Perez-Garcia et al. Via a reduction given in that paper,

this answers a 35-year-old problem in operator algebras due to Varopoulos,

showing that the space of compact operators on a Hilbert space is a Q-algebra

under Schur product.

A further generalization of Grothendieck's inequality due to Carne lets us

show that the gap between the entangled and classical value is at most a

constant in any multiplayer XOR game in which the players are allowed to share

combinations of GHZ states and EPR pairs of any dimension.

As an application of our results, we show that the discrepancy method in

communication complexity remains a lower bound in the multiparty model where

the players have quantum communication and the kinds of entanglement discussed

above. This answers an open question of Lee, Schechtman, and Shraibman.

#### Projects

**Selected projects**