Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-071 | 1st September 2009 20:46

Kolmogorov Complexity in Randomness Extraction

RSS-Feed




TR09-071
Authors: John Hitchcock, A. Pavan, N. V. Vinodchandran
Publication: 3rd September 2009 08:40
Downloads: 3094
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