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