ECCC-Report TR15-017https://eccc.weizmann.ac.il/report/2015/017Comments and Revisions published for TR15-017en-usSat, 31 Jan 2015 16:01:39 +0200
Paper TR15-017
| Linear list-approximation for short programs (or the power of a few random bits) |
Bruno Bauwens,
Marius Zimand
https://eccc.weizmann.ac.il/report/2015/017A $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$. We also show a polynomial-time randomized construction that achieves the same list size for $O(\log^2 n)$-short programs. These results beat the lower bounds shown by Bauwens et al.~\cite{bmvz:c:shortlist} for deterministic constructions of such lists. We also prove tight lower bounds for the main parameters of our result. The constructions use only $O(\log n)$ ($O(\log^2 n)$ for the polynomial-time result) random bits. Thus using only few random bits it is possible to do tasks that cannot be done by any deterministic algorithm regardless of its running time.Sat, 31 Jan 2015 16:01:39 +0200https://eccc.weizmann.ac.il/report/2015/017