Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGORITHMIC INFORMATION THEORY:
Reports tagged with algorithmic information theory:
TR00-026 | 11th April 2000
Andrei Romashchenko, Alexander Shen, Nikolay Vereshchagin

#### Combinatorial Interpretation of Kolmogorov Complexity

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

TR06-006 | 16th December 2005
Alexander Shen

#### Multisource algorithmic information theory

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

TR10-128 | 15th August 2010
Scott Aaronson

#### The Equivalence of Sampling and Searching

Revisions: 1

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

TR21-071 | 16th May 2021
Samuel Epstein

#### On the Algorithmic Content of Quantum Measurements

We show that given a quantum measurement, for an overwhelming majority of pure states, no meaningful information is produced. This is independent of the number of outcomes of the quantum measurement. Due to conservation inequalities, such random noise cannot be processed into coherent data.

more >>>

TR22-175 | 16th November 2022
Samuel Epstein

#### Derandomization Under Different Resource Constraints

Revisions: 1

We provide another proof to the EL Theorem. We show the tradeoff between compressibility of codebooks and their communication capacity. A resource bounded version of the EL Theorem is proven. This is used to prove three instances of resource bounded derandomization.

more >>>

ISSN 1433-8092 | Imprint