Arıkan meets Shannon: Polar codes with asymptotically fast convergence to channel capacity
Prof. Venkatesan Guruswami
Computer Science Department
Carnegie Mellon University
Join via Zoom:
tum-conf.zoom.us/j/99659928638
Meeting ID: 996 5992 8638
Passcode: 550777
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 W be an arbitrary binary-input memoryless symmetric channel with Shannon capacity I(W), and fix any delta > 0. We construct binary linear codes of length N and rate I(W) - O(N^{-0.5+delta}) that enable reliable communication on W with efficient encoding and decoding. Previously such a construction was only known for the erasure channel. An inverse square-root rate of convergence to capacity is information-theoretically the best possible, and matches the non-constructive bounds implied by Shannon's theorem.
Our codes are a variant of Arıkan's celebrated polar codes. We employ multiple carefully constructed local kernels in the recursive construction of polar codes, 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 just above capacity.
Based on joint work with Andrii Riazanov and Min Ye.
Biography:
Venkatesan Guruswami (Venkat) is a Professor in the Computer Science Department at Carnegie Mellon University, and the director of its Ph.D. program. He received his Ph.D. from the Massachusetts Institute of Technology in 2001, and was a Miller Research Fellow at UC Berkeley during 2001-02.
Venkat’s research interests include error-correcting codes, approximate optimization, constraint satisfaction, pseudorandomness, and related complexity-theoretic and mathematical aspects. Venkat serves on the editorial board of the Journal of the ACM and was till recently the Editor-in-Chief of the ACM Transactions on Computation Theory. He has (co)-chaired the program committees of the Computational Complexity Conference (CCC’12), Symposium on Foundations of Computer Science (FOCS’15), and the International Symposium on Information Theory (ISIT’18). Venkat is currently President of the Computational Complexity Foundation (CCF) and a co-moderator for arXiv/cs.IT (Information Theory).
Venkat is a Fellow of the ACM and the IEEE. He was an invited speaker at the 2010 International Congress of Mathematicians on the topic of ``Mathematical Aspects of Computer Science.'' His other honors include the EATCS Presburger Award, Packard and Sloan Fellowships, a Google Faculty Research Award, the ACM Doctoral Dissertation Award, and an IEEE Information Theory Society Paper Award. He was recently named a Simons Investigator in theoretical computer science by the Simons Foundation.