General Strong Polarization
Madhu Sudan (Harvard)
In this talk we will introduce and explain the "polarization of bounded martingales". This concept came to the fore in a brilliant invention from 2008 by Arikan, who build a powerful class of error-correcting codes called Polar codes, and whose analysis depended on the polarization of a specific bounded martingale. Sufficiently strong analysis of this martingale eventually led to a resolution, in 2013, of a fundamental algorithmic challenge arising from Shannon's seminal 1948 work.
In this talk I will introduce bounded martingales, define polarization and explain how polarization can be analyzed very generally, using elementary techniques. In the second half of the talk I will describe Arikan's polarization technique and the martingale that arises from it, and show how our analysis methods apply to his martingale. Together these results give a simple, complete and general proof of the resolution of the afore-mentioned algorithmic challenge.
Based on joint works with Jaroslaw Blasiok, Venkatesan Gurusawmi, Preetum Nakkiaran, and Atri Rudra (STOC 2018, RANDOM 2018, and ITCS 2019).