Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

ISSN 1433-8092 | Imprint