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 theoretical computer science and related mathematics. This is a theoretically oriented graduate course, though mathematically sophisticated undergraduates should also find the course stimulating. Starting from 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 such topics include polar coding to achieve Shannon capacity; list decoding for optimal recovery against worst-case errors; locally decodable codes to correct errors very efficiently; graph based codes and efficient iterative decoders; algebraic-geometric codes; connections between coding theory and pseudorandomness; codes in distributed storage (locally repairable codes/regenerating codes); codes for combating synchronization errors; coding for interactive communication, etc. 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 3-5 problem sets (precise instructions will be given on each problem set), attendance and class participation. It is strongly recommended that students attend all lectures, as detailed notes beyond what is linked to below may not be available. Depending upon schedule and student inteerst, 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.
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.
The lecture notes from the Fall 2014 offering of course, and the earlier Spring 2010 offering (which also featured a course blog with lecture summaries) will also be useful.