Polarization and randomness extraction

Emmanuel Abbe

doi:10.1109/ISIT.2011.6033870

Polarization and randomness extraction

Emmanuel Abbe

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 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 language	English (US)
Title of host publication	2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Pages	184-188
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2011.6033870
State	Published - 2011
Event	2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 - St. Petersburg, Russian Federation Duration: Jul 31 2011 → Aug 5 2011

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8104

Other

Other	2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011
Country/Territory	Russian Federation
City	St. Petersburg
Period	7/31/11 → 8/5/11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Information Systems
Modeling and Simulation
Applied Mathematics

Access to Document

10.1109/ISIT.2011.6033870

Cite this

@inproceedings{f3c7a2191bdb425c8750cfa904e93a2c,

title = "Polarization and randomness extraction",

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.",

author = "Emmanuel Abbe",

year = "2011",

doi = "10.1109/ISIT.2011.6033870",

language = "English (US)",

isbn = "9781457705953",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "184--188",

booktitle = "2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011",

note = "2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011 ; Conference date: 31-07-2011 Through 05-08-2011",

}

Abbe, E 2011, Polarization and randomness extraction. in 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011., 6033870, IEEE International Symposium on Information Theory - Proceedings, pp. 184-188, 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011, St. Petersburg, Russian Federation, 7/31/11. https://doi.org/10.1109/ISIT.2011.6033870

TY - GEN

T1 - Polarization and randomness extraction

AU - Abbe, Emmanuel

PY - 2011

Y1 - 2011

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

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

UR - http://www.scopus.com/inward/record.url?scp=80054808786&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054808786&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2011.6033870

DO - 10.1109/ISIT.2011.6033870

M3 - Conference contribution

AN - SCOPUS:80054808786

SN - 9781457705953

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 184

EP - 188

BT - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

T2 - 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011

Y2 - 31 July 2011 through 5 August 2011

ER -

Polarization and randomness extraction

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this