Computer Science Thesis Proposal

  • Gates Hillman 8102 and Zoom
  • In Person and Virtual ET
  • Ph.D. Student
  • Ph.D. Program in Algorithms, Combinatorics, Optimization
  • Computer Science Department, Carnegie Mellon University
Thesis Proposals

Polar codes with near-optimal convergence to channel capacity

The performance of an error-correcting code is evaluated by its code rate, block error probability, construction algorithm complexity, and encoding and decoding complexities. For any coding channel, its Shannon capacity is the maximal rate of error-correcting codes which can allow nearly error-free communication through this channel, the notion introduced by Claude E. Shannon in his seminal work in 1948. Finding explicit families of codes with rates that approach Shannon capacity and which also have good performance in all other aspects simultaneously has been one of the central challenges in coding theory for many decades.

In this thesis, we present a family of codes which resolves this challenge for all binary-input memoryless symmetric coding channels. The rates of our codes approach Shannon capacity and they approach it optimally fast, meaning that they have the best possible scaling of their block-length as a function of the gap to capacity. At the same time, encoding and decoding complexities are quasi-linear in block-length, and the decoding error probability is inverse sub-exponential, which is also almost optimal. Previously error-correcting codes which attain all these properties at the same time were only known for the binary erasure channel, in our work we generalize it for a much wider universe of channels.

The codes we present are a variant of Arikan's polar codes based on multiple carefully constructed local kernels. For ongoing and future work, we propose extending these results for an even wider range of channels and settings, as well as improving the way the local kernels are chosen in our current construction.

Thesis Committee:
Venkat Guruswami (Chair)
Ryan O'Donnell
Pravesh Kothari
Alexander Barg (University of Maryland)

In Person and Zoom Participation. See announcement.

For More Information, Please Contact: