Polarization and randomness extraction

Emmanuel Auguste Abbe

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

This paper explores a connection between randomness extraction and channel (source) coding problems. It is explained how efficient extractors can be used to define efficient coding schemes and reciprocally, a new deterministic extractor based on a polar coding scheme is proposed. Since the source model used in extractors for computer science (cryptography) do not assume i.i.d. or known distributions, a generalized polarization phenomenon for sources with block memory and unknown distributions is developed. It is shown that in this setting, the min-entropy (as usual in extractors) rather than Shannon entropy can be efficiently extracted. The derived polar coding results also apply to compound channels with memory.

Original languageEnglish (US)
Title of host publication2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages184-188
Number of pages5
DOIs
StatePublished - Oct 26 2011
Externally publishedYes
Event2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation
Duration: Jul 31 2011Aug 5 2011

Other

Other2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
CountryRussian Federation
CitySt. Petersburg
Period7/31/118/5/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Polarization and randomness extraction'. Together they form a unique fingerprint.

  • Cite this

    Abbe, E. A. (2011). Polarization and randomness extraction. In 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 (pp. 184-188). [6033870] https://doi.org/10.1109/ISIT.2011.6033870