The next TCS+ talk will take place this coming Wednesday, April 1th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Venkat Guruswami from CMU will speak about “Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity” (abstract below).
You can reserve a spot as an individual or a group to join us live by signing up on the online form. (The link will also be posted on our website on the day of the talk, so people who did not sign up will still be able to join, until the maximum capacity of 300 seats is reached.) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: We establish a constructive version of Shannon’s noisy coding theorem for binary codes, with information rate converging near-optimally fast to channel capacity as a function of code length. Specifically, let be an arbitrary binary-input memoryless symmetric channel with Shannon capacity , and fix any . We construct, for any sufficiently small , binary linear codes of block length and rate that enable reliable communication on with quasi-linear time encoding and decoding. Shannon’s theorem implies the existence of such codes (without efficient constructions or decoding) with block length . This quadratic dependence on the gap epsilon to capacity is known to be best possible. Previously such a construction was only known for the case of the erasure channel.
Our codes are a variant of Arıkan’s polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A key technical ingredient in the analysis is a strong converse to the noisy coding theorem that shows extreme unpredictability of even a single message bit when communicating via random linear codes at rates slightly above capacity.
Joint work with Andrii Riazanov and Min Ye.