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 9, 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
- Piazza
Join the course Piazza If you are unable to join because you do not have an MIT email address, please email the course staff with the email address you would like to use, and we will add you.
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, q-ary entropy, GV Bound, Singleton Bound | Lecture 2 notes Chapters 2, 3, and 4 GRS |
| Lecture 03 | Rohan Goyal | Dual Codes; Hadamard code; Plotkin Bound; Reed-Solomon codes | Lecture 3 notes Chapters 4 and 5 GRS |
| Lecture 04 | Rohan Goyal | Channel capacity, list decoding, and the Johnson, Elias–Bassalygo, and MRRW bounds | Lecture 4 notes Chapters 6–8 GRS |
| 02Interactive coding theory | |||
| Lecture 05 | Yael Kalai | Interactive coding and tree codes | Lecture 5 notes Problem set 1 |
| Lecture 06 | Yael Kalai | Interactive coding (continued) | Lecture 6 notes |
| Lecture 07 | Yael Kalai | Tree codes | Lecture 7 notes |
| Lecture 08 | Yael Kalai | Computationally efficient interactive coding | Lecture 8 notes |
| 03Code constructions | |||
| Lecture 09 | Guest: Tim Hsieh | Concatenated codes and expanders | Chapter 10 GRS |
| No class | — | — | Indigenous Peoples' Day · Institute holiday |
| Lecture 10 | Rohan Goyal | Expander codes | Lecture 10 notes Chapter 11 GRS Lecture 17 Sud08 Monday schedule of classes |
| Lecture 11 | Rohan Goyal | Polynomial Codes | Lecture 11 notes Chapter 9 GRS Lecture 8 Har22 (pp. 3–8) Problem set 2 |
| 04Subspace designs and LCL properties | |||
| Lecture 12 | Rohan Goyal | — | — |
| Lecture 13 | Rohan Goyal | — | — |
| Lecture 14 | Rohan Goyal | — | — |
| Lecture 15 | Rohan Goyal | — | — |
| 05Algorithms | |||
| Lecture 16 | — | — | — |
| Lecture 17 | — | — | — |
| Midterm | — | — | Midterm |
| 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 |
Problem sets
Problem set writeups do not need to be submitted. If none of the available presentation slots work for you, please email Rohan to arrange another time.
| Problem set | Released | Due | Solution presentation scheduling |
|---|---|---|---|
| Problem set 1 | September 23, 2026 | October 7, 6:00 PM | Schedule a presentation |
| Problem set 2 | October 15, 2026 | October 28, 6:00 PM | Schedule a presentation |
References
- [GRS]
Venkatesan Guruswami, Atri Rudra, and Madhu Sudan, Essential Coding Theory, draft book.
- [Gur22]
Venkatesan Guruswami, CS 294-226: Advances in Error-Correcting Codes, UC Berkeley, Fall 2022.
- [Har22]
Prahladh Harsha, CSS.318.1: Coding Theory, TIFR, Monsoon 2022.
- [Har24]
Prahladh Harsha, CSS.318.1: Coding Theory, TIFR, 2024.
- [Kop22]
Swastik Kopparty, Topics in Error Correcting Codes, University of Toronto, Fall 2022.
- [Sud08]
Madhu Sudan, 6.440: Essential Coding Theory, MIT, Spring 2008.
- [Sud23]
Madhu Sudan, Essential Coding Theory, course materials.
- [Woo25]
Mary Wootters, CS250/EE387: Error-Correcting Codes, Stanford University, Winter 2025. Lecture videos.
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.
Project ideas: Download the project ideas (PDF) for reading topics, suggested papers, and research directions. 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 9 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.