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 CNFs, ... more >>>

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 >>>

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 additive term ... more >>>

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 >>>