2013/11/28 by Bruno Bauwens, Bauwens, Bruno, Marius Zimand +1
Computer Science · #68Q17 #68Q30 #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.2.3 #FOS: Computer and information sciences #Machine Learning and Algorithms #acm:68Q17 #acm:68Q30 #cs.CC #msc:68Q17 #msc:68Q30
paper · pdf · doi:10.48550/arxiv.1311.7278
openalex publication_date 2013/11/28 · arxiv created 2015/01/20 · arxiv updated 2015/01/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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(log2 n)-short programs. These results beat the lower bounds shown by Bauwens et al. \citebmvz: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(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.