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

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

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.

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

The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs
to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted
using information on the word $x_1, x_2, ...., x_t $ only. We use the game
theoretical interpretation which can be traced to Laplace where there ... 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 ... 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 ... 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 ... 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.

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.

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.

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

It is a trivial observation that every decidable set has strings of length $n$ with Kolmogorov complexity $\log n + O(1)$ if it has any strings of length $n$ at all. Things become much more interesting when one asks whether a similar property holds when one
considers *resource-bounded* Kolmogorov complexity. ... more >>>

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability
distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input
$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set
$A_{x}$ with high probability. ... more >>>

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>

In \cite{shenpapier82}, it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems ... more >>>

We consider the following problem that arises in outsourced storage: a user stores her data $x$ on a remote server but wants to audit the server at some later point to make sure it actually did store $x$. The goal is to design a (randomized) verification protocol that has the ... more >>>