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