Kolmogorov Complexity in Randomness Extraction
ACM Transactions on Computation Theory · 2011
DOI: 10.1145/2003685.2003686 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von John M. Hitchcock und 2 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 15 Literaturangaben. Gefördert von: National Science Foundation.
Abstract (Originalsprache)
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 Mk 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 Mk .
Förderung
- National Science Foundation
Zitieren
APA
Hitchcock, J. M., Pavan, A., & Vinodchandran, N. V. (2011). Kolmogorov Complexity in Randomness Extraction. ACM Transactions on Computation Theory. https://doi.org/10.1145/2003685.2003686
Vancouver
Hitchcock JM, Pavan A, Vinodchandran NV. Kolmogorov Complexity in Randomness Extraction. ACM Transactions on Computation Theory. 2011. doi:10.1145/2003685.2003686
BibTeX
@article{Hitchcock2011,
author = {Hitchcock, John M. and Pavan, A. and Vinodchandran, N. V.},
title = {Kolmogorov Complexity in Randomness Extraction},
journal = {ACM Transactions on Computation Theory},
year = {2011},
doi = {10.1145/2003685.2003686}
}
EUVIMED