EUVIMEDEUVIMED entdecken
Crossref

Kolmogorov Complexity in Randomness Extraction

John M. Hitchcock, A. Pavan, N. V. Vinodchandran

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →