EPFL doctorate Award 2019 – Rajai Nasser

"For outstanding contributions to the foundations of polar codes and the topology of channels."

Information theory is the field in which we study the fundamental limitations of communication. Shannon proved in 1948 that there exists a maximum rate, called capacity, at which we can reliably communicate information through a given channel. However, Shannon did not provide an explicit construction of a practical capacity-achieving coding scheme. Polar coding, invented by Arikan, is the first low-complexity coding technique that achieves the capacity of binary-input memoryless symmetric channels.

This thesis consists of two parts. In the first part, we investigate several problems in the theory of polar codes. We determine the binary operations that always lead to polarization when they are used in Arikan-style constructions. We use Fourier analysis to characterize all the multiple-access channels whose symmetric capacity regions are conserved by polarization. We also construct polar codes for arbitrary classical-quantum channels.
In the second part of this thesis, we investigate three orderings of communication channels: degradedness, input-degradedness, and the Shannon ordering. We provide several characterizations for the input-degradedness and the Shannon ordering. We construct various topologies on the space of discrete memoryless channels, and we study the continuity of several channel parameters and operations under these topologies.