Linear list-approximation for short programs (or the power of a few random bits)

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(logn)-short program for x. We also show a polynomial-time randomized construction that achieves the same list size for O(log2 n)-short programs. These results beat the lower bounds shown by Bauwens et al. [1] for deterministic constructions of such lists. We also prove tight lower bounds for the main parameters of our result. The constructions use only O(logn) (O(log2 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