General Strong Polarization
Madhu Sudan (Harvard)
The classical theorem of Shannon asserts that the capacity of the binary symmetric channel with paremeter p is (1 - h(p)) where h(p) is the binary entropy function. More elaborately it says that if we choose any epsilon > 0, then for sufficiently large n, there are codes of block length n, rate at least 1 - h(p) - epsilon that can correct random bit flip errors with high probability, where each bit is flipped independently with probability p. Forney's technique of concatenated codes (from 1966) shows how to do this with polynomial time algorithms, where the algorithms run in time polynomial in n for every fixed epsilon. However the dependence on epsilon remained exponentially high.
Arikan's introduction of Polar codes in 2008 suggested a possibility that we may have finally found a technique to reduce the dependence to be polynomial in epsilon. Five years later in 2013, Guruswami and Xia, and independently Hassani, Alishahi and Urbanke finally confirmed this possibilty thus resolving a major open question in the Shannon theory.
In our work we give clean modular explanations of the main theorem above, which also yields generalizations to a broader class of codes, and broader class of channels (including channels with some memory) and yield exponentially low probabiity of decoding failure (of the form exp(-n^Omega(1)).
Based on joint works with Jaroslaw Blasiok, Venkatesan Gurusawmi, Preetum Nakkiaran, and Atri Rudra (STOC 2018, RANDOM 2018, and ITCS 2019).