Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR09-071 | 1st September 2009 20:46

Kolmogorov Complexity in Randomness Extraction

TR09-071
Authors: John Hitchcock, A. Pavan, Vinodchandran Variyam
Publication: 3rd September 2009 08:40
Downloads: 1515
Keywords:

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

ISSN 1433-8092 | Imprint