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.