Topics in Coding Theory (Spring 2025)

Instructor: Shashank Srivastava

Time: Mondays and Wednesdays 2-3:20 PM at TIL - 242 (Tillett Hall)
Course Number: 16:198:674

Course Description: 

Error-correcting codes are mathematical objects designed to withstand corruption. Originally intended for use in practical communication over noisy channels, codes have now become an important object of study in Theoretical Computer Science due to their connections to complexity theory, pseudorandomness, etc. The study of codes involves a fascinating interplay of randomness, algebra and algorithms.

In the first part of the course, we will introduce the basics of coding theory, highlighting the associated combinatorial and algorithmic challenges. We will then discuss how the standard constructions of codes meet these challenges, and the several large gaps that remain in our understanding. We will also discuss some applications outside coding theory.

In the second part, we will discuss some recent developments in the field of coding theory. The goal will be to illustrate what contemporary research looks like in the area. See the syllabus below for a tentative list of topics to be discussed.

Prerequisites: 

This is an introductory graduate-level course intended primarily for students interested in Theoretical Computer Science or Discrete Math. It will be expected that the students have basic exposure to topics like linear algebra, probability, algorithms, as well as the mathematical maturity to write rigorous proofs.

Evaluation: 

There will be 2 homeworks, carrying 40% of the grade. 50% of the grade will be based on the final project, which will include an in-class presentation and a report. The remaining 10% will be based on scribing one lecture.

Homework 1 (Due Feb 26)

Homework 2 (Due May 1)

Syllabus:

Part I:

1. Basics of error-correction, and random constructions

2. Algebraic constructions of codes

3. Codes from expander graphs

4. Decoding algorithms: algebraic and combinatorial

5. List Decoding

6. Locality in codes: LTCs, LDCs and LCCs

7. Applications

Part II:

8. Quantum LDPC codes and connections to LTCs

9. Near-optimal explicit binary codes

10. Lower bounds for LCCs/LDCs

11. Decoding algorithms via Sum-of-Squares

12. Generalized Singleton bound and constructions achieving it

References:

Essential Coding Theory, book by Guruswami, Rudra and Sudan