CS 294-226: Advances in Error-Correcting Codes, Fall 2022

Instructor: Venkatesan Guruswami.
Lecture time: MW, 10:30-11:59am, SODA 320, starting Aug 24.
TA: Omar Alrabiah.
Office hours: Venkat: Mondays 4-5pm; Omar: Thursdays 2-4pm.

Ed discussion page

Course Description: Error-correcting codes play an important role in many areas of science and engineering, as they safeguard the integrity of data against the adverse effects of noise in communication and storage. They have also become important tools in the theory of computing and discrete mathematics.Starting with a fast-paced review of the basics of coding theory and some of the classic theorems (and challenges) of the subject, the course will move to a subset of several modern (still actively researched) topics in code constructions and error-correction algorithms. Possible topics include algebraic codes and decoding algorithms; polar codes for achieving Shannon capacity; list decoding for optimal recovery against worst-case errors; locally decodable and repairable codes to correct errors very efficiently; graph based codes and efficient iterative decoders; locally testable codes; quantum error-correcting codes; connections between coding theory and pseudorandomness; codes for combating synchronization errors; coding for interactive communication, etc. The goal is to expose students to some of the exciting frontiers and recent developments in the field, and in order to accomplish this goal within the allotted lecture time, students will be expected to do readings that supplement the lectures, especially in the beginning to get a good grounding on the basics of coding theory. This is a theoretically oriented graduate course targeted at EECS and Math PhD students, though mathematically sophisticated undergraduates should also find the course stimulating and may take the course with instructor permission. At the end of the course, the students should have a good grounding in coding theory and various approaches to construct good codes, and also be able to read, appreciate, and understand some of the current research literature in the subject.

Grading: Grades will be assigned based on a few (3 to 5) problem sets, attendance and class participation. It is strongly recommended that students attend all lectures. Students will be expected to produce a high quality scribe of one lecture during the semester. Depending upon schedule and enrollment size, we might have some form of final project such as summarizing (with a solid understanding) some research paper(s), partial progress on some research problem, etc. There will be no exams.

Course materials/text

Here is a book in writing that develops the fundamental aspects of coding theory in a gentle manner. Also available are individual chapters of (an older version of) the book. We will not follow the book per se and often deviate from (and cover topics outside) it as well, but it will still be a useful supplementary reference.

This page from the Fall 2018 offering of a similar course (at Carnegie Mellon) should also have useful notes and resources.

Lecture scribe notes

Problem sets

Additional referenes

Some (mostly older) surveys that could be useful for the course: