Survey on Polar Codes

Madhu Sudan (Harvard)

The discovery of Polar Codes by Arikan 2008, along with the efficient decoder he gave for these codes suggested the possibility that a long standing question in algorithmic coding theory may finally be resolved: Namely a family of codes that gets epsilon close to capacity (on say the binary symmetric channel) at block lengths polynomial in 1/epsilon, with polynomial encoding and decoding times. The possibility was eventually confirmed in 2013 in independent works of Guruswami and Xia; and Hassani, Alishahi and Urbanke.

In this talk we will survey these codes focussing on (1) The efficient decoding algorithm for the binary error channel and (2) the finite block length question. The latter in particular leads to elegant questions about the rate of convergence of bounded martingales and we will describe a general tool that allows us to analyze their convergence. 

Some of the proofs in the talk are from joint work(s) with Blasiok, Guruswami, Nakkiran and Rudra (STOC 2018, Random 2018, JACM 2022).