LIPIcs.FSTTCS.2009.2320.pdf
- Filesize: 210 kB
- 12 pages
Document
Kolmogorov Complexity in Randomness Extraction
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2009-12-14
Cite As Get BibTex
John M. Hitchcock, Aduri Pavan, and N. V. Vinodchandran. Kolmogorov Complexity in Randomness Extraction. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 215-226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2320
Abstract
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$.
Subject Classification
Keywords
- Extractors
- Kolmogorov extractors
- randomness
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads