#### Can supervise: YES

#### Publications

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

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

Childs, AM & Lee, T 2008, 'Optimal Quantum Adversary Lower Bounds for Ordered Search', pp. 869-880.View/Download from: Publisher's site

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.

Gavinsky, D, Lee, T, Santha, M & Sanyal, S, 'A composition theorem for randomized query complexity via max conflict complexity'.

#### View description

Let $R_\epsilon(\cdot)$ stand for the bounded-error randomized query

complexity with error $\epsilon > 0$. For any relation $f \subseteq \{0,1\}^n

\times S$ and partial Boolean function $g \subseteq \{0,1\}^m \times \{0,1\}$,

we show that $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot

\sqrt{R_{1/3}(g)})$, where $f \circ g^n \subseteq (\{0,1\}^m)^n \times S$ is

the composition of $f$ and $g$. We give an example of a relation $f$ and

partial Boolean function $g$ for which this lower bound is tight.

We prove our composition theorem by introducing a new complexity measure, the

max conflict complexity $\bar \chi(g)$ of a partial Boolean function $g$. We

show $\bar \chi(g) \in \Omega(\sqrt{R_{1/3}(g)})$ for any (partial) function

$g$ and $R_{1/3}(f \circ g^n) \in \Omega(R_{4/9}(f) \cdot \bar \chi(g))$; these

two bounds imply our composition result. We further show that $\bar \chi(g)$ is

always at least as large as the sabotage complexity of $g$, introduced by

Ben-David and Kothari.

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.

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.

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, 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 & 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.

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, '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 & 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 & 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 & 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.