A note on the sign degree of formulas (2009)
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,...
Harry Buhrman, Troy Lee, Dieter Van Melkebeek
The language compression problem asks for succinct descriptions of the strings in a language A such that the strings can be efficiently recovered from their description when given a membership oracle...
Kolmogorov Complexity with Error (2008)
Lance Fortnow, Troy Lee, Nikolai Vereshchagin
Abstract. We introduce the study of Kolmogorov complexity with error. For a metric d, we define Ca(x) to be the length of a shortest program p which prints a string y such that d(x, y) ≤ a. We also...
Product theorems via semidefinite programming (2008)
Abstract. 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...
An approximation algorithm for approximation rank (2008)
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...
Rutgers University ∗ Abstract (2008)
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;...
The formula size of PARITY (2008)
We exactly determine the formula size of the parity function. If n = 2 ℓ + k, where 0 ≤ k < 2 ℓ, then the formula size of parity on n bits is 2 ℓ (2 ℓ + 3k) = n 2 + k2 ℓ − k 2....
The quantum adversary method and (2008)
Sophie Laplante, Troy Lee, Mario Szegedy
classical formula size lower bounds
Kolmogorov Complexity with Error (2008)
Lance Fortnow, Troy Lee, Nikolai Vereshchagin
visiting CWI. Abstract. We introduce the study of Kolmogorov complexity with error. For a metric d, we define Ca(x) to be the length of a shortest program p which prints a string y such that d(x, y)...
Kolmogorov complexity and formula size lower bounds (2008)
Troy Lee, Formula Size, Lower Bounds, Academisch Proefschrift, Troy Jeffrey Lee, Promotor Prof. Dr, ...
ter verkrijging van de graad van doctor aan de Universiteit van Amsterdam op gezag van de Rector Magnificus prof.mr. P.F. van der Heijden ten overstaan van een door het college voor promoties...
A direct product theorem for discrepancy (2008)
Discrepancy is a versatile bound in communication complexity which can be used to show lower bounds in the distributional, randomized, quantum, and even unbounded error models of communication. We...
Approximation norms and duality for communication complexity lower bounds (2008)
Abstract: We will discuss a general norm based framework for showing lower bounds on communication complexity. An advantage of this approach is that one can use duality theory to obtain a lower bound...
Arithmetical Denability over Finite Structures (2007)
Arithmetical denability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical denability over nite structures, motivated by the correspondence...
Optimal quantum adversary lower bounds for ordered search (2007)
The goal of the ordered search problem is to find a particular item in an ordered list of n items. Using the adversary method, Hoyer, Neerbek, and Shi proved a quantum lower bound for this problem of...
Negative weights make adversaries stronger (2007)
The quantum adversary method is one of the most successful techniques for proving lower bounds on quantum query complexity. It gives optimal lower bounds for many problems, has application to...
A new rank technique for formula size lower bounds (2007)
We introduce a new technique for proving formula size lower bounds based on matrix rank. A simple form of this technique gives bounds at least as large as those given by the method of Khrapchenko,...
The quantum adversary method and (2005)
Sophie Laplante, Troy Lee, Mario Szegedy
classical formula size lower bounds
The quantum adversary method and (2005)
Sophie Laplante, Troy Lee, Mario Szegedy
classical formula size lower bounds
Arithmetical definability over finite structures (2002)
Arithmetical definability has been extensively studied over the natural numbers. In this paper, we take up the study of arithmetical definability over finite structures, motivated by the...
On `hot spot' contention (1985)
This thesis owes a lot to David Mix Barrington, as it was a conversation with him that brought the problems discussed here to my attention. It was also series of lectures given by him the year before...