Welcome to CS250/EE387!
Algebraic Error Correcting Codes
Stanford University, Winter 2025.
Course Overview
Instructor: Mary Wootters
CA: Keller Blackwell
Course Description:
Introduction to the theory of error correcting codes, emphasizing algebraic constructions and diverse applications throughout computer science and engineering. Topics include basic bounds on error correcting codes; Reed-Solomon and Reed-Muller codes; list-decoding, list-recovery and locality. Applications may include communication, storage, complexity theory, pseudorandomness, cryptography, streaming algorithms, group testing, and compressed sensing.
Prerequisites:
Linear algebra, basic probability (at the level of, say, CS109, CME106 or EE178) and "mathematical maturity" (students will be asked to write proofs). Familiarity with finite fields will be helpful but not required.
What do I need to do? In-class work, three homework assignments, and a project.
How to attend:
- Class is M/W, 9:30-10:50am, in CERAS 300.
- Lecture videos are pre-recorded and available on YouTube on this playlist.
Office Hours:
- Mary's OH: Mondays 3-5pm, CoDa W216. [Note: Mary's OH are shared with CS265/CME309]
- Keller's OH: Thursdays 11am-1pm, CoDa 221.
Any deviations to the schedule will be announced on Canvas.
Course Structure
This course is being run as a flipped classroom, which means you will watch lecture videos before coming to class, and during class we will work on group work problems that reinforces or extends the lecture material.
Here are the course elements:
- Lecture Videos. The lecture videos are pre-recorded and available here.
- Homework.
There will be three homeworks. You do not have to do the entire homework assignments, but the more you do the more you will learn.
See Homework below for more details.
- Project. You will work with a small group on a class project for last few weeks of the course. The project can take lots of different forms. See Assignments below for more details.
- In-class time. During in-class time, we will meet in person and work on problems. Links to these problems, and the solutions, are available below in the schedule, so you can follow along even if you have to miss a class or two.
Announcements
Please see our Canvas page for all announcements.
Assignments
There will be three required homeworks and a project. There is also in-class work that will not be graded.
- Homeworks are due on some-but-not-all Fridays, by 11:59pm.
- Homework will be turned in on Gradescope. (Please email the course staff list if you don't have access).
- Homework will be done in small groups (up to three people). Please turn in one assignment per group. Make sure to put all your names on the assignment, and to use the "group assignment" feature in Gradescope.
- We encourage you to type your homework. Overleaf is a great option for group LaTeX-ing; we will provide LaTeX templates for each HW. If you must hand-write, please make sure that your handwriting is extremely clear. Unclear homework and/or bad scans will be returned without being graded.
- Homework will be accepted up to three days late, with a penalty of 5% per day late. That said,
we will be reasonable about extensions, with the understanding that no homework can be accepted after solutions are posted. Please email the course staff list if you need an extension.
- Here is some more information about the project, which you will work on in small groups.
- Project Proposal due 11:59pm Friday 2/14, on Gradescope.
- Project Write-up due 11:59pm Friday 3/14, on Gradescope. (The last day of classes).
- Project Presentations will take place during Week 10.
Some groups will do in-person presentations (3/10 and 3/12), and some will pre-record videos (due 3/11), according to their reported preference; all groups should plan for a 12 minute presentation.
Which group is doing which format is included in a Canvas announcement.
You can find more information on the presentation in the final project guidelines document linked above.
Homework Assignments
Advice: DO NOT START THE HOMEWORK AT THE LAST MINUTE. There are only three homework assignments, spaced 2-3 weeks apart; each one represents 2-3 weeks of work. The questions are labeled with when you will have the background to do them in order to make time management easier. The due dates and class schedule are such that you should be able to start the next HW as soon as you turn the previous one in. Solutions will be posted on Canvas.
Policies
Other course policies
- Grading Policy: 28% project, 72% HW. Each HW is worth the same amount, 24% of your grade.
- There will be lots of opportunities to do more than the assigned work: lots of optional HW problems, and the project can be as big as you want to make it.
You can get an A in this class without doing any of that.
If you want an A+ in this class (or, more importantly, just want to learn more), do a bit more than the required amount: eg, each week do 4-5 Section 2 problems instead of 3; or really engage with some of the Section 3 problems; or go over the top on your project. This bonus work won't affect your grade directly in any other way, although it will hopefully affect your learning!
We are happy to chat with you about as much extra work as you want to do (although we won't grade it)---just reach out if you'd like to chat!
- Collaboration policy: collaboration is encouraged! If you collaborate on HW outside your HW group, please acknowledge your collaborators. (Note: While collaboration is encouraged, plagiarism is never okay. Everything that you and your HW group turns in should be in y'all's own words.)
- LLM policy: We view LLMs like ChatGPT to be incredibly useful tools, similar to a knowedgeable friend. Thus, the same rules apply to LLMs as apply to such a friend (outside your homework group): you are welcome to chat with them to get intuition, insight or pointers. But you shouldn't ask them to do/write up your homework for you, just like you shouldn't ask your friend to do/write up your homework for you.
Accommodations and flexibility
If you are in a situation that makes the format of this class especially difficult for you, please reach out. (Email the staff list or contact Mary directly). We will try to make this course work for you.
Students who may need academic accommodations based on the impact of a disability should initiate the request with the Office of Accessible Education (OAE) and notify us as soon as possible by emailing the course staff list:
cs250-win2425-staff@lists.stanford.edu
Monday 1/6. Class 1: Introduction! Basics of ECCs.
- Videos: L1.V1: Motivation; L1.V2: Definitions; L1.V3: Hamming Bound. (NOTE: since this is the first class, we're not expecting you to watch the videos before class. We'll go over some of this material during the first class, and you can either look at the lecture notes or watch the videos afterwards to fill in the gaps.)
- Further reading:
- In-Class problems
- In-Class solutions
Wednesday 1/8. Class 2: Intro to finite fields; linear codes
- Videos: L2.V1: The Hamming Code Revisited; L2.V2: A Cautionary Tale; L2.V3: Finite Fields; L2.V4: Linear Codes
- Further reading:
- Lecture Notes
- (Optional) Essential Coding Theory, Chapter 2.
- For more background about finite fields, check out Essential Coding Theory, Appendix D.
- In-Class problems
- In-Class solutions
Monday 1/13. Class 3: More linear codes; McEliece Cryptosystem; Asymptotics, Hamming and GV bounds.
- Videos: L3.V1: GV Bound; L3.V2: Efficient Algorithms?; L3.V3: McEliece; L3.V4: Asymptotics; L3.V5: q-ary Entropy
- Further reading:
- In-Class problems
- In-Class solutions
Wednesday 1/15. Class 4: Singleton and Plotkin bounds; Reed-Solomon Codes!!
- Videos: L4.V1: Singleton bound; L4.V2: Plotkin bound; L4.V3: Polynomials over finite fields; L4.V4: REED-SOLOMON CODES!!!!; L4.V5: Dual view of RS codes
- Further reading:
- Lecture Notes
- (Optional) Essential Coding Theory, 4.3,4.4, Chapter 5.
- In-Class problems
- In-Class solutions
Wednesday 1/22. Class 5: The Welch-Berlekamp Algorithm
- Videos: L5.V1 History of RS codes; L5.V2 Welch-Berlekamp.
- Further reading:
- Lecture Notes
- Note: There's some optional reading in the lecture notes about the Berlekamp-Massey algorithm, but it won't be covered in the videos.
- (Optional) Essential Coding Theory, 15.1.
- In-Class problems
- In-Class solutions
Monday 1/27. Class 6: Binary Codes! BCH Codes, Reed-Muller (take 1), Code Concatenation (take 1)
- Videos: L6.V1 Binary RS codes?; L6.V2 BCH Codes; L6.V3 RM Codes; L6.V4 Concatenated Codes
- Further reading:
- Lecture Notes
- (Optional) Essential Coding Theory, 10.1 (for concatenated codes)
- In-Class problems
- In-Class solutions
Wednesday 1/29. Class 7: More concatenated codes and the Zyablov bound
- Videos: L7.V1: Zyablov bound; L7.V2: Algorithms for concatenated codes Part 1; L7.V3: Algorithms for concatenated codes Part 2.
- Further reading:
- In-Class problems
- In-Class solutions
Monday 2/3. Class 8: Relationships to other problems: compressed sensing and group testing
- Videos: L8.V1: Syndrome Decoding, Compressed Sensing, and Group Testing; L8.V2: Disjunct Matrices; L8.V3: The Kautz-Singleton Construction
- Further reading:
- Lecture Notes
- (Optional) Essential Coding Theory, Ch 19 (for group testing).
- In-Class problems
- In-Class solutions
Wednesday 2/5. Class 9: Random errors and efficiently achieving capacity on the BSC
- Videos: L9.V1: Random Errors; L9.V2: Capacity of the BSC; L9.V3: Efficiently achieving capacity on the BSC
- Further reading:
- In-Class problems
- In-Class solutions
Monday 2/10. Class 10: List Decoding; List-decoding capacity thm and Johnson Bound.
- Videos: L10.V1: List-Decoding; L10.V2: List-Decoding Capacity Theorem; L10.V3: The Johnson Bound
- Further reading:
- In-Class problems
- In-Class solutions
Wednesday 2/12. Class 11: Guruswami-Sudan Algorithm
- Videos: L11.V1: Useful facts about bivariate polynomials; L11.V2: The problem we want to solve; L11.V3: Sudan's algorithm; L11.V4: Guruswami-Sudan Algorithm
- Further reading:
- In-Class problems
- In-Class solutions
Monday 2/17.
- No class (President's Day)
Wednesday 2/19. Class 12: List-Recovery and Applications
- Videos: L12.V1: List-Recovery; L12.V2: List-Recovery of RS codes; L12.V3: Heavy Hitters; L12.V4: Applications of list-recovery (including heavy hitters).
- Further reading:
- In-Class problems
- In-Class solutions
Monday 2/24. Class 13: Folded RS Codes
- Videos: L13.V1: Folded RS Codes; L13.V2: List-Decoding FRS Codes, Take 1; L13.V3: List-Decoding FRS Codes, Take 2
- Further reading:
- In-Class problems
- In-Class solutions
Wednesday 2/26. Class 14: Reed-Muller Codes and Locality
- Videos: L14.V1: Locally Correctable Codes; L14.V2: Locally Correcting Hadamard Codes; L14.V3: Locally Correcting Reed-Muller Codes
- Further reading:
- In-Class problems
- In-Class solutions
Monday 3/3. Class 15: Local List-Decoding and Applications (Goldreich-Levin; Kushilevitz-Mansour)
- Videos: L15.V1: Motivation: Learning Boolean Functions; L15.V2: Goldreich-Levin Algorithm; L15.V3: Local List-Decoding and Applications
- Further reading:
- In-Class problems
- In-Class solutions
Wednesday 3/5. Class 16: RS Codes as Regenerating Codes in Distributed Storage
- Videos: L16.V1: Regerating Codes; L16.V2: The field trace; L16.V3: RS codes as regenerating codes.
- Further reading:
- No in-class exercises! Instead, Mary and Keller will talk about some of their recent/current research (related to today's topic).
Monday 3/10. Class 17: Project presentations
Wednesday 3/12. Class 18: Project presentations