2026-08-07T04:52:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2320 2024-03-06T10:33:17Z ddc:004 open_access

Kolmogorov Complexity in Randomness Extraction Hitchcock, John M. Pavan, Aduri Vinodchandran, N. V. Extractors Kolmogorov extractors randomness We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction and randomness extraction. We present a distribution ${\cal M}_k$ based on Kolmogorov complexity that is complete for randomness extraction in the sense that a computable function is an almost randomness extractor if and only if it extracts randomness from ${\cal M}_k$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik John M. Hitchcock and Aduri Pavan and N. V. Vinodchandran 2009 Is Part Of LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2009.2320 urn:nbn:de:0030-drops-23201 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2320 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode