General Strong Polarization
Jaroslaw Blasiok, Preetum Nakkiran, Madhu Sudan (Harvard)
A martingale is a sequence of random variables that maintain their future expected value conditioned on the past. A $[0,1]$-bounded martingale (where the random variables are always in $[0,1]$) is said to polarize if it converges in the limit to either $0$ or $1$ with probability $1$. A martingale is said to polarize strongly, if in $ steps it is sub-exponentially close to its limit with all but exponentially small probability.
Martingale polarization came to the fore in 2008, when Arikan built a powerful class of error-correcting codes called Polar codes based on this idea. The essence of his theory associates a martingale with every invertible square matrix over a field (and a channel) and showed that polarization of the martingale leads to a construction of codes that converge to Shannon capacity. In 2013, Guruswami and Xia, and independently Hassani et al. showed that the martingale associated with the simplest $2x2$ matrix considered in Arikan's work polarizes strongly, and this led to the first construction of codes that converge to Shannon capacity at finite block lengths, specifically at lengths that are inverse polynomial in the gap to capacity, thereby resolving a major mathematical challenge associated with the attainment of Shannon capacity.
Prior to our work strong polarization was poorly understood and the only matrix that was known to polarize strongly was the 2x2 matrix alluded to above. We show that a simple necessary condition for an invertible matrix to polarize over any non-trivial channel is also sufficient for strong polarization over all symmetric channels over all prime fields. In addition to the generality of our result, it also leads to arguably simpler proofs. The essence of our proof is a local definition of polarization which only restricts the evolution of the martingale in a single step, and a general theorem showing the local polarization suffices for strong polarization.
In this talk we will introduce polarization and polar codes and present a full proof of our main theorem. No prior background on polar codes will be necessary.
Based on joint work with Venkatesan Guruswami (CMU), and Atri Rudra (Buffalo).