General Strong Polarization

Madhu Sudan (CS, Harvard)

A recent discovery (circa 2008) in information theory called Polar Coding has led to a remarkable construction of error-correcting codes and decoding algorithms, resolving one of the fundamental algorithmic challenges in the field. The underlying phenomenon studies the ``polarization'' of a ``bounded'' martingale. A bounded martingale, X_0,...,X_t,...  is one where X_t in [0,1]. This martingale is said to polarize if Pr[lim_{t\to infty} X_t \in {0,1}] = 1. The questions of interest to the results in coding are the rate of convergence and proximity: Specifically, given epsilon and tau > 0 what is the smallest t after which it is the case that Pr[X_t in (tau,1-tau)] < epsilon? For the main theorem, it was crucial that t <= min{O(log(1/epsilon)), o(log(1/tau))}. We say that a martingale polarizes strongly if it satisfies this requirement. We give a simple local criterion on the evolution of the martingale that suffices for strong polarization. A consequence to coding theory is that a broad class of constructions of polar codes can be used to resolve the afore-mentioned algorithmic challenge.

In this talk I will introduce the concepts of polarization and strong polarization.  Depending on the audience interest I can explain why this concept is useful to construct codes and decoding algorithms, or explain the local criteria that help establish strong polarization (and the proof of why it does so).

Based on joint work with Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran,
and Atri Rudra.