Computer Science Speaking Skills Talk

Wednesday, March 4, 2020 - 12:00pm to 1:00pm


3305 Newell-Simon Hall



Arikan meets Shannon: Polar codes with near-optimal convergence to channel capacity

Let be a binary-input memoryless symmetric (BMS) channel with Shannon capacity I(W) and fix any α>0. We construct, for any sufficiently δ>0, binary linear codes of block length O(1/δ2+α) and rate I(W)−δ that enable reliable communication on W with quasi-linear time encoding and decoding. Shannon's noisy coding theorem established the existence of such codes (without efficient constructions or decoding) with O(1/δ2). This quadratic dependence on the gap δ to capacity is known to be the best possible. Our result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel.

Our codes are a variant of Arikans polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.

Joint work with Venkat Guruswami and Min Ye.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

For More Information, Contact:


Speaking Skills