All reports by Author Troy Lee:

__
TR17-123
| 2nd August 2017
__

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs#### Quadratically Tight Relations for Randomized Query Complexity

__
TR17-107
| 1st June 2017
__

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal#### A Composition Theorem for Randomized Query complexity

Revisions: 1

__
TR16-072
| 4th May 2016
__

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha#### Separations in communication complexity using cheat sheets and information complexity

__
TR15-098
| 15th June 2015
__

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs#### Separations in Query Complexity Based on Pointer Functions

Revisions: 2

__
TR13-158
| 18th November 2013
__

GĂˇbor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta#### Information-theoretic approximations of the nonnegative rank

Revisions: 3

__
TR08-003
| 25th December 2007
__

Troy Lee, Adi Shraibman#### Disjointness is hard in the multi-party number-on-the-forehead model

__
TR04-080
| 7th September 2004
__

Lance Fortnow, Troy Lee, Nikolay Vereshchagin#### Kolmogorov Complexity with Error

__
TR04-031
| 22nd March 2004
__

Troy Lee, Andrei Romashchenko#### On Polynomially Time Bounded Symmetry of Information

__
TR04-002
| 8th January 2004
__

Troy Lee, Dieter van Melkebeek, Harry Buhrman#### Language Compression and Pseudorandom Generators

Dmytro Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs

Let $f:\{0,1\}^n \rightarrow \{0,1\}$ be a Boolean function. The certificate complexity $C(f)$ is a complexity measure that is quadratically tight for the zero-error randomized query complexity $R_0(f)$: $C(f) \leq R_0(f) \leq C(f)^2$. In this paper we study a new complexity measure that we call expectational certificate complexity $EC(f)$, which is ... more >>>

Anurag Anshu, Dmytro Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal

Let the randomized query complexity of a relation for error probability $\epsilon$ be denoted by $\R_\epsilon(\cdot)$. We prove that for any relation $f \subseteq \{0,1\}^n \times \mathcal{R}$ and Boolean function $g:\{0,1\}^m \rightarrow \{0,1\}$, $\R_{1/3}(f\circ g^n) = \Omega(\R_{4/9}(f)\cdot\R_{1/2-1/n^4}(g))$, where $f \circ g^n$ is the relation obtained by composing $f$ and $g$. ... more >>>

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G\"o{\"o}s, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha

While exponential separations are known between quantum and randomized communication complexity for partial functions, e.g. Raz [1999], the best known separation between these measures for a total function is quadratic, witnessed by the disjointness function. We give the first super-quadratic separation between quantum and randomized

communication complexity for a ...
more >>>

Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs

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})$. ...
more >>>

GĂˇbor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta

Common information was introduced by Wyner as a measure of dependence of two

random variables. This measure has been recently resurrected as a lower bound on the logarithm of the nonnegative rank of a nonnegative matrix. Lower bounds on nonnegative rank have important applications to several areas such

as communication ...
more >>>

Troy Lee, Adi Shraibman

We show that disjointness requires randomized communication

Omega(\frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}})

in the general k-party number-on-the-forehead model of complexity.

The previous best lower bound was Omega(\frac{log n}{k-1}). By

results of Beame, Pitassi, and Segerlind, this implies

2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver

proof systems needed to refute certain unsatisfiable ...
more >>>

Lance Fortnow, Troy Lee, Nikolay Vereshchagin

We introduce the study of Kolmogorov complexity with error. For a

metric d, we define C_a(x) to be the length of a shortest

program p which prints a string y such that d(x,y) \le a. We

also study a conditional version of this measure C_{a,b}(x|y)

where the task is, given ...
more >>>

Troy Lee, Andrei Romashchenko

The information contained in a string $x$ about a string $y$

is defined as the difference between the Kolmogorov complexity

of $y$ and the conditional Kolmogorov complexity of $y$ given $x$,

i.e., $I(x:y)=\C(y)-\C(y|x)$. From the well-known Kolmogorov--Levin Theorem it follows that $I(x:y)$ is symmetric up to a small ...
more >>>

Troy Lee, Dieter van Melkebeek, Harry Buhrman

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 for

A. We study randomized and nondeterministic decompression schemes

and investigate how close we can get to the information ...
more >>>