Polarization and randomness extraction

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.