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

• ACM Transactions on Computation Theory, 3(1), article 1, 2011.
  [DOI]
  
  
• Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (Kanpur, India, December 15-17, 2009), pages 215--226. Leibniz International Proceedings in Informatics, 2009.
  [DOI | PDF]
  
  
• Technical Report TR09-071, Electronic Colloquium on Computational Complexity, 2009.
  [PDF]