more >>>

C.H.~Bennett, P.~G\'acs, M.~Li, P.M.B.~Vit\'anyi, and W.H.~Zurek have defined information distance between two strings $x$, $y$ as $$ d(x,y)=\max\{ K(x|y), K(y|x) \} $$ where $K(x|y)$ is the conditional Kolmogorov complexity. It is easy to see that for any string $x$ and any integer $n$ there is a string $y$ such that ... more >>>

The very first Kolmogorov's paper on algorithmic information theory was entitled `Three approaches to the definition of the quantity of information'. These three approaches were called combinatorial, probabilistic and algorithmic. Trying to establish formal connections between combinatorial and algorithmic approaches, we prove that any linear inequality involving Kolmogorov complexities could ... more >>>

A string $p$ is called a program to compute $y$ given $x$ if $U(p,x)=y$, where $U$ denotes universal programming language. Kolmogorov complexity $K(y|x)$ of $y$ relative to $x$ is defined as minimum length of a program to compute $y$ given $x$. Let $K(x)$ denote $K(x|\text{empty string})$ (Kolmogorov complexity of $x$) ... more >>>

Predictive complexity is a generalization of Kolmogorov complexity which gives a lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A variety of types of loss functions makes it interesting to study relations between corresponding predictive complexities. Non-linear inequalities between predictive complexity of non-logarithmic ... more >>>

We obtain the following full characterization of constructive dimension in terms of algorithmic information content. For every sequence A, cdim(A)=liminf_n (K(A[0..n-1])/n. more >>>

We present a simplified proof of Solovay-Calude-Coles theorem stating that there is an enumerable undecidable set with the following property: prefix complexity of its initial segment of length n is bounded by prefix complexity of n (up to an additive constant). more >>>

Assume that for almost all n Kolmogorov complexity of a string x conditional to n is less than m. We prove that in this case there is a program of size m+O(1) that given any sufficiently large n outputs x. more >>>

We study different notions of descriptive complexity of computable sequences. Our main result states that if for almost all n the Kolmogorov complexity of the n-prefix of an infinite binary sequence x conditional to n is less than m then there is a program of length m^2+O(1) that for almost ... more >>>

We define Kolmogorov complexity of a set of strings as the minimal Kolmogorov complexity of its element. Consider three logical operations on sets going back to Kolmogorov and Kleene: (A OR B) is the direct sum of A,B, (A AND B) is the cartesian product of A,B, (A --> B) ... more >>>

We invistigate what is the minimal length of a program mapping A to B and at the same time mapping C to D (where A,B,C,D are binary strings). We prove that it cannot be expressed in terms of Kolmogorv complexity of A,B,C,D, their pairs (A,B), (A,C), ..., their triples (A,B,C), ... more >>>

We consider sets of strings with high Kolmogorov complexity, mainly in resource-bounded settings but also in the traditional recursion-theoretic sense. We present efficient reductions, showing that these sets are hard and complete for various complexity classes. In particular, in addition to the usual Kolmogorov complexity measure K, we consider the ... 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 >>>

A recursive enumerator for a function $h$ is an algorithm $f$ which enumerates for an input $x$ finitely many elements including $h(x)$. $f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$ is among the first $k(n)$ elements enumerated by $f$. If there is a $k(n)$-enumerator for ... more >>>

Solovay has proven that the minimal length of a program enumerating a set A is upper bounded by 3 times the absolute value of the logarithm of the probability that a random program will enumerate A. It is unknown whether one can replace the constant 3 by a smaller constant. ... 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 >>>

We investigate the question of whether one can characterize complexity classes (such as PSPACE or NEXP) in terms of efficient reducibility to the set of Kolmogorov-random strings R_C. We show that this question cannot be posed without explicitly dealing with issues raised by the choice of universal machine in the ... more >>>

Let a program p on input a output b. We are looking for a shorter program p' having the same property (p'(a)=b). In addition, we want p' to be simple conditional to p (this means that the conditional Kolmogorov complexity K(p'|p) is negligible). In the present paper, we prove that ... 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 >>>

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings require Omega(sqrt(n)) bit flips. For a given m, we also give bounds for increasing ... more >>>

We apply recent results on extracting randomness from independent sources to ``extract'' Kolmogorov complexity. For any $\alpha, \epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show how to use a constant number of advice bits to efficiently compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) > (1-\epsilon)|y|$. ... more >>>

We show that under a reasonable hardness assumptions, the time-bounded Kolmogorov distribution is a universal samplable distribution. Under the same assumption we exactly characterize the worst-case running time of languages that are in average polynomial-time over all P-samplable distributions. more >>>

Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity. more >>>

We define a new discrete version of scaled dimension and we find connections between the scaled dimension of a string and its Kolmogorov complexity and predictability. We give a new characterization of constructive scaled dimension by Kolmogorov complexity, and prove a new result about scaled dimension and prediction. more >>>

We present a brief survey of results on relations between the Kolmogorov complexity of infinite strings and several measures of information content (dimensions) known from dimension theory, information theory or fractal geometry. Special emphasis is laid on bounds on the complexity of strings in constructively given subsets of the Cantor ... more >>>

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily close ... more >>>

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of non-random information by computational depth, the difference between the polynomial-time-bounded Kolmogorov complexity and traditional Kolmogorov complexity We show how to find satisfying assignments for formulas that have at least one assignment of logarithmic depth. The converse holds under a standard ... more >>>

A very important problem in quantum communication complexity is to show that there is, or isn?t, an exponential gap between randomized and quantum complexity for a total function. There are currently no clear candidate functions for such a separation; and there are fewer and fewer randomized lower bound techniques that ... more >>>

We continue an investigation into resource-bounded Kolmogorov complexity \cite{abkmr}, which highlights the close connections between circuit complexity and Levin's time-bounded Kolmogorov complexity measure Kt (and other measures with a similar flavor), and also exploits derandomization techniques to provide new insights regarding Kolmogorov complexity. The Kolmogorov measures that have been introduced ... more >>>

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction ... more >>>