Title: POLAR CODES: FROM THEORY TO PRACTICE
Abstract: The discovery of polar codes is widely regarded as THE major breakthrough in coding theory in the past decade. These codes provably achieve the capacity of any discrete memoryless symmetric channel, with low encoding and decoding complexity. We will start with a brief primer on polar codes, and some of their applications beyond point-to-point communications.

Until recently, however, polar codes were mainly of theoretical interest, since two key obstacles prevented their utilization in practice. Polar codes certainly cannot be used in practice unless there is an efficient method to *construct* them. Although numerous heuristics for this problem have been proposed, none produced a construction algorithm that runs in polynomial time and provides explicit guarantees on the quality of its output. In this talk, we will describe an algorithm that does just that. Our algorithm is based on the idea of channel degrading/upgrading and runs in linear time. It works extremely well in practice, and has become the de facto standard for constructing polar codes.

Another key problem in the theory of polar codes was that of improving their performance at short and moderate code lengths. It has been observed empirically that polar codes do not perform as well as turbo codes or LDPC codes at such lengths. However, we have recently showed that significant gains can be attained using a *list-decoding algorithm* for polar codes. Our algorithm retains the desirable properties of the conventional decoder, such as low complexity and recursive structure. Simulations on the BPSK-modulated AWGN channel show that, already at length 2048, list-decoding of polar codes outperforms the best-known LDPC codes (e.g. the LPDC code used in the WiMax standard).