Algorithmic coding theory: Some recent advances

Lecturer: Professor Venkatesan Guruswami (Carnegie Mellon University, USA).

About the lecturer | Course Summary | Lecture Notes | Assignment

About the lecturer: Venkatesan Guruswami received his Bachelor's degree from the Indian Institute of Technology at Madras in 1997 and his Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2001. He is currently an Associate Professor in the Computer Science Department at Carnegie Mellon University. He is a theoretical computer scientist with rather broad interests, including the theory of error-correcting codes, pseudorandomness, approximation algorithms, hardness of approximation, probabilistically checkable proofs, and algebraic algorithms. His work on list decoding has led to codes with minimum possible redundancy for correcting any desired fraction of worst-case errors. Dr. Guruswami currently serves on the editorial boards of the SIAM Journal on Computing, IEEE Transactions on Information Theory, and the ACM Transactions on Computation Theory, and was program committee chair for the 2012 Computational Complexity conference. He was an invited speaker at the 2010 International Congress of Mathematicians, and received the Presburger Award in 2012. His earlier honors include the Packard and Sloan Fellowships, the ACM Doctoral Dissertation Award, and the IEEE Information Theory Society Paper Award.

Course summary: Error-correcting codes safeguard data against the adverse effects of noise during communication and storage. They are vital for ensuring the reliable operation of much of the digital technology in everyday use today. An error-correcting code provides a judicious way to encode data into codewords, incorporating enough redundancy in the process to enable recovery of the original data even from codewords corrupted by noise. One of principal goals of coding theory is to construct codes with minimum possible redundancy for various noise models, along with efficient algorithms for error correction using those codes. Over the decades, this subject has witnessed a rich body of work, drawing upon diverse techniques from combinatorics, linear algebra, graph theory, probability, field theory, and algebraic geometry to construct good coding schemes.

This mini-course will begin with a quick introduction to the basic motivations and concepts of coding theory, and some of the classical code constructions. With the requisite background in place, it will then focus on some more recent algorithmic advances, such as list decodable codes that can correct an error fraction as large as the redundancy of the code, and locally decodable codes which can correct errors by randomly probing a tiny portion of the codeword. The construction of polar codes for achieving capacity of certain probabilistic channels might also be discussed. The course may also briefly touch upon some of the rich connections between coding theory and pseudorandomness.

Lecture Notes: These notes go into some more detail (and some historical contexts) than the lecture covered, but that might be a useful supplement for those interested.

  1. Introduction and Basics
  2. The Gilbert-Varshamov bound and related calculations
  3. Reed-Solomon and concatenated codes construction (the notes also has BCH and Reed-Muller codes which we didn't have a chance to discuss)
  4. Justesen codes, Reed-Solomon decoding, and concatenated codes decoding
  5. Reed-Solomon list decoding
  6. Folded Reed-Solomon codes (we gave a simpler "entirely" linear-algebraic argument which has been discovered since. The best reference at this point may be Section 2 of this paper.)

Assignment: The problem set is here.
Please send solutions (PDF) to Bartek Klin (klin@[you-know-what]) by December 6, 2012.