#### Can supervise: YES

#### Publications

Lee, T, Mittal, R, Reichardt, BW, palek, R & Szegedy, M 2011, 'Quantum Query Complexity of State Conversion', *2011 IEEE 52nd Annual Symposium on Foundations of Computer Science*.View/Download from: Publisher's site

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 & Mittal, R, 'Product theorems via semidefinite programming'.

#### View description

The tendency of semidefinite programs to compose perfectly under product has

been exploited many times in complexity theory: for example, by Lovasz 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 Lovasz, and a direct product theorem

for the discrepancy method of communication complexity by Lee, Shraibman, and

Spalek.

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.

Lee, T & Shraibman, A, 'An approximation algorithm for approximation rank'.

#### View description

One of the strongest techniques available for showing lower bounds on quantum

communication complexity is the logarithm of the approximation rank of the

communication matrix--the minimum rank of a matrix which is entrywise close to

the communication matrix. This technique has two main drawbacks: it is

difficult to compute, and it is not known to lower bound quantum communication

complexity with entanglement.

Linial and Shraibman recently introduced a norm, called gamma_2^{alpha}, to

quantum communication complexity, showing that it can be used to lower bound

communication with entanglement. Here the parameter alpha is a measure of

approximation which is related to the allowable error probability of the

protocol. This bound 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 alpha-approximation rank, rk_alpha. We show that in fact

log gamma_2^{alpha}(A)$ and log rk_{alpha}(A)$ agree up to small factors. As

corollaries we obtain a constant factor polynomial time approximation algorithm

to the logarithm of approximate rank, and that the logarithm of approximation

rank is a lower bound for quantum communication complexity with entanglement.

Lee, T & Shraibman, A, 'Disjointness is hard in the multi-party number on the forehead model'.

#### View description

We show that disjointness requires randomized communication

Omega(n^{1/(k+1)}/2^{2^k}) in the general k-party number-on-the-forehead model

of complexity. The previous best lower bound for k >= 3 was log(n)/(k-1). Our

results give a separation between nondeterministic and randomized multiparty

number-on-the-forehead communication complexity for up to k=log log n - O(log

log log n) many players. Also by a reduction of Beame, Pitassi, and Segerlind,

these results imply subexponential lower bounds on the size of proofs needed to

refute certain unsatisfiable CNFs in a broad class of proof systems, including

tree-like Lovasz-Schrijver proofs.

Lee, T, Magniez, F & Santha, M, 'Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing'.

#### View description

We show that the quantum query complexity of detecting if an $n$-vertex graph

contains a triangle is $O(n^{9/7})$. This improves the previous best algorithm

of Belovs making $O(n^{35/27})$ queries. For the problem of determining if an

operation $\circ : S \times S \rightarrow 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. As in our previous work, the edge slots

maintained in the database are specified by a graph whose edges are the union

of regular bipartite graphs, the overall structure of which mimics that of the

graph of the certificate. By allowing these bipartite graphs to be unbalanced

and of variable degree we obtain better algorithms.

Lee, T, Prakash, A, Wolf, RD & Yuen, H, 'On the sum-of-squares degree of symmetric quadratic functions'.

#### View description

We study how well functions over the boolean hypercube of the form

$f_k(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

$\ell_{\infty}$-norm as well as in $\ell_1$-norm. We describe three

complexity-theoretic applications: (1) a proof that the recent breakthrough

lower bound of Lee, Raghavendra, and Steurer 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

$\ell_1$-approximation of $f_k$; (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 his work; (3) bounds on the query

complexity of quantum algorithms whose expected output approximates such

functions.

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

Ambainis, A, Balodis, K, Belovs, A, Lee, T, Santha, M & Smotrovs, J, 'Separations in Query Complexity Based on Pointer Functions'.

#### View description

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=2^k$ bits defined by a complete

binary tree of NAND gates of depth $k$, which achieves $R_0(f) =

O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total

boolean function $f$ on $n$ bits whose deterministic query complexity is

$\Omega(n/\log(n))$ while its zero-error randomized query complexity is $\tilde

O(\sqrt{n})$. We further show that the quantum query complexity of the same

function is $\tilde O(n^{1/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 $\Omega(n/\log(n))$ and bounded-error

randomized query complexity $R(g) = \tilde O(\sqrt{n})$. This is the first

super-linear separation between these two complexity measures. The exact

quantum query complexity of the same function is $Q_E(g) = \tilde O(\sqrt{n})$.

These two functions show that the relations $D(f) = O(R_1(f)^2)$ and $R_0(f)

= \tilde O(R(f)^2)$ are optimal, up to poly-logarithmic factors. Further

variations of these functions give additional separations between other query

complexity measures: a cubic separation between $Q$ and $R_0$, a $3/2$-power

separation between $Q_E$ 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.

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

#### 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 $\frac{1}{m} + \frac{m-1}{m}

t^{1-t}$. Secondly, for free XOR games, in which the input distribution is of

product form, we show $\beta(G) \geq \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-\mathcal{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.

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.

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

#### View description

A well-studied class of functions in communication complexity are composed

functions of the form $(f \comp 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 \comp g^n)$, and in

what way.

Recently, Sherstov \cite{She09b} and independently Shi-Zhu \cite{SZ09b}

developed conditions on the inner function $g$ which imply that the quantum

communication complexity of $f \comp 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 {\em strongly balanced}---we say that $g: X \times Y \to \{-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 \cite{She09b}, which has been a very useful idea in a variety of

settings \cite{She08b,RS08,Cha07,LS09,CA08,BHN09}.

Shi-Zhu require that the inner function $g$ has small {\em 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.

#### Projects

**Selected projects**