Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

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

Alexander Shen

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

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