Massachusetts Institute of Technology · Electrical Engineering and Computer Science
6.S953: Topics in Error-Correcting Codes for Computer Science
Fall 2026 · Graduate · 12 units
This topics course in error-correcting codes begins with the fundamentals, progresses to the research frontier, and explores recent developments in the field.
- Professor
- Yael T. Kalai
tauman@mit.edu - TA / co-lecturer
- Rohan Goyal
rohan_g@mit.edu - Time
- Mon & Wed
11:00–12:30 - Location
- 36-156
Overview
This topics course in error-correcting codes begins with the fundamentals, progresses to the research frontier, and explores recent developments in the field. Principal areas include existence results and limitations for error-correcting codes, constructions and algorithms, interactive coding, subspace designs, and applications in computer science.
Prerequisites
6.1200, 6.1210, and 18.06.
Syllabus
The course is organized into the following modules. Lecture-level topics, notes, and references will be added to the schedule as the course develops. The midterm is scheduled for November 2, and the final two class meetings are reserved for project presentations.
- Foundations: Possibilities and limitations; Chapters 1–8 of GRS
- Interactive coding theory: Limitations of and improvements to error correction through interaction and feedback
- Code constructions: Algebraic and combinatorial techniques; Chapters 9–11 of GRS and more recent developments
- Subspace designs and LCL properties: Constructions of subspace-design codes, combinatorial techniques for list decoding, and equivalences among LCL properties
- Algorithms: List-decoding algorithms for Reed-Solomon and expander-based codes
- Applications: A range of applications across theoretical computer science
Logistics
- Level and units
Graduate · 12 units
- Prerequisites
6.1200, 6.1210, and 18.06
- Requirement
AAGS in Theoretical Computer Science
Schedule
Classes meet Mondays and Wednesdays from 11:00–12:30. Calendar exceptions are noted below.
| Course no. & date | Lecturer | Topic | Notes & references |
|---|---|---|---|
| 01Foundations | |||
| Lecture 01 | Yael Kalai | Introduction and basics | Lecture 1 notes Chapter 1 (GRS) |
| Lecture 02 | Rohan Goyal | Linear codes and q-ary entropy | Chapters 2 and 3 GRS |
| Lecture 03 | Rohan Goyal | GV and Singleton bounds; Reed-Solomon and MDS codes | Chapters 4 and 5 GRS |
| Lecture 04 | Rohan Goyal | List-decoding bounds: capacity, Johnson, and generalized Singleton | Chapters 6–8 GRS |
| 02Interactive coding theory | |||
| Lecture 05 | Yael Kalai | The interactive and feedback models | — |
| Lecture 06 | Yael Kalai | — | — |
| Lecture 07 | Yael Kalai | — | — |
| Lecture 08 | Yael Kalai | — | — |
| 03Code constructions | |||
| Lecture 09 | Guest: Tim Hsieh | Concatenated codes and expanders | — |
| No class | — | — | Indigenous Peoples' Day · Institute holiday |
| Lecture 10 | Rohan Goyal | Expander codes | Monday schedule of classes |
| Lecture 11 | Rohan Goyal | Polynomial Codes | — |
| 04Subspace designs and LCL properties | |||
| Lecture 12 | — | — | — |
| Lecture 13 | — | — | — |
| Lecture 14 | — | — | — |
| Lecture 15 | — | — | — |
| Midterm | — | — | Midterm |
| 05Algorithms | |||
| Lecture 16 | — | — | — |
| Lecture 17 | — | — | — |
| No class | — | — | Veterans Day · Institute holiday |
| Lecture 18 | — | — | — |
| Lecture 19 | — | — | — |
| 06Applications | |||
| Lecture 20 | — | — | — |
| Lecture 21 | — | — | — |
| Lecture 22 | — | — | — |
| Lecture 23 | — | — | — |
| Project presentations | — | — | Presentations |
| Project presentations | — | — | Presentations · Last course meeting |
References
- [GRS]
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan, Essential Coding Theory, draft book.
- [Sud23]
Madhu Sudan, Essential Coding Theory, course materials.
- [Har24]
Prahladh Harsha, CSS.318.1: Coding Theory, TIFR, 2024.
- [Woo25]
Mary Wootters, CS250/EE387: Error-Correcting Codes, Stanford University, Winter 2025. Lecture videos.
- [Gur22]
Venkatesan Guruswami, CS 294-226: Advances in Error-Correcting Codes, UC Berkeley, Fall 2022.
- [Kop22]
Swastik Kopparty, Topics in Error Correcting Codes, University of Toronto, Fall 2022.
Policies
Evaluation
The grade will be based on the following three components:
- Course project — 50%. See the project details and timeline below.
- In-class midterm — 20%.
- Problem sets — 30%. See the problem-set details below.
Project
The project is completed in groups of two or three and may take one of two forms: research or reading.
Candidate projects for both forms will be added soon. You may also propose a topic that aligns with the course, subject to approval by the professor or TA. You may schedule a meeting with Rohan to discuss possible projects and ideas.
Project timeline:
- October 2 at 6:00 PM — Topic and group selection (5%).
- October 16 at 6:00 PM — One-page project proposal and plan (10%).
- November 13 at 6:00 PM — One-page progress report (10%).
- December 7 and 9 — Project presentations (15%).
- December 11 — Eight- to ten-page project report or paper (10%).
Problem sets
There will be four problem sets, and the final grade will be based on your three highest scores. Each problem set will contain four to six problems, of which you are expected to solve at least three. You will then schedule a 15-minute meeting with the TA to present your solutions and answer questions about the three problems you chose.
Collaboration
Students may collaborate with classmates and use AI models to discuss course material. We strongly recommend limiting AI use to supporting understanding rather than solving problems. Students are responsible for all content in their projects, presentations, and submitted work.