All reports by Author Bruno Bauwens:

__
TR15-017
| 20th January 2015
__

Bruno Bauwens, Marius Zimand#### Linear list-approximation for short programs (or the power of a few random bits)

__
TR13-007
| 8th January 2013
__

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand#### Short lists with short programs in short time

Revisions: 1

Bruno Bauwens, Marius Zimand

A $c$-short program for a string $x$ is a description of $x$ of length at most $C(x) + c$, where $C(x)$ is the Kolmogorov complexity of $x$. We show that there exists a randomized algorithm that constructs a list of $n$ elements that contains a $O(\log n)$-short program for $x$. ... more >>>

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>