## 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.

- Introduction and Basics
- The Gilbert-Varshamov bound and related calculations
- Reed-Solomon and concatenated codes construction (the notes also has BCH and Reed-Muller codes which we didn't have a chance to discuss)
- Justesen codes, Reed-Solomon decoding, and concatenated codes decoding
- Reed-Solomon list decoding
- 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**.