15-859Y: Coding Theory, Fall 2014

Instructor: Venkatesan Guruswami.
Lecture time: Monday, Wednesday & Friday, 3:00-4:20 PM, GHC 5222.
(We will meet regularly on Mon & Wed, we will only have lectures on about 5-6 Fridays. Upcoming Friday lectures: Oct 3, 10, 24. No class on Monday Oct 20.)
Office hours: By appointment.

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. 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 of the subject, the course will discuss code constructions and error-correction algorithms in 3-4 actively studied topics, such as polar coding to achieve Shannon capacity; list decoding to correct worst-case errors with optimal redundancy; locally decodable codes to correct errors very efficiently; graph based codes with efficient iterative decoders; connections between coding theory and pseudorandomness/computational complexity theory, etc.


Problem sets


Course notes


Project Ideas

Project presentations:


Grading: Grades will be assigned based on 3-5 problem sets (precise instructions will be given on each problem set), attendance and class participation, and 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.


References/Text: The above linked notes will be the main reference.
You can also visit the Spring 2010 course webpage, or the course blog for that offering.

There is no textbook for the course, but here is a book in writing that develops the fundamental aspects of coding theory in a gentle manner. We won't be following this book per se, but it could be a useful supplementary reference.