CS250/EE387

Welcome to CS250/EE387!

Algebraic Error Correcting Codes

Stanford University, Winter 2022.

Course Overview

Instructor: Mary Wootters

CA: Nolan Miranda

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:45-11:15am. Starting Feb. 7, we are back in-person in CERAS 300.
  • Our OhYay space is still open for watch parties/office hours/hanging out. You can access our class space at ohyay.co/s/cs250. If you are enrolled in the course, you can click here to get the password. (If you are not enrolled but want to regularly attend class, please email marykw to discuss and to get the password; during the shopping period you can also find the password on Canvas, which we are otherwise not using).
  • Lecture videos will be pre-recorded and available on YouTube on this playlist.
  • Office Hours and Watch Parties:
    • Mary's OH: Mondays 2-4pm on Zoom. You can find the link on OhYay, in the "Mary's Office" room.
    • Watch parties with Nolan: Sundays and Tuesdays at 7:00pm, on OhYay.
    Any deviations to the schedule will be announced in the Announcement box on this page, and also on Ed.

    • 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. All of them are already available. 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

    • 2/28/22: The final presentation schedule and the assignments for which remote presentations to watch are available here. Note that there are two tabs, one for in-person presentations and one for remote presentations. Please let me know ASAP if there is an issue with this schedule.
    • 2/25/22: More information about the final presentations have been posted. See the last page of the guidance doc.
    • 2/20/22: Mary's OH are cancelled on President's day (2/21). Please reach out if you'd like to meet some other time this week.
    • 2/5/22: Based on the results of the new poll, we will be back in person starting Week 6 (Feb 7). See you in CERAS 300!
    • 1/25/22: Based on results of the poll, we will be on OhYay through the end of Week 5 (Feb 3) at least. There will be another poll soon to make a decision about after that.
    • 1/22/22: We are still on OhYay for Monday 1/24.
    • 1/17/22: Mary's OH are cancelled on MLK day. Please reach out if you'd like to meet some other time this week.
    • 1/15/22: Please fill out this poll to register how you feel about in-person instruction: (Click here!) by Sunday 1/16/22 evening.
    • 1/14/22: Some of the text in problem 4 on HW1 was misleading, it's been updated.
    • 1/12/22: Please fill out this poll to register how you feel about how class is going! (Click here!)

    Useful Links

    Assignments

    There will be three required homeworks and a project. There is also in-class work that will not be graded.

    Homework Policies

    • Homeworks are due on some-but-not-all Fridays, by 11:59pm.
    • Homework will be turned in on Gradescope. Entry code: 6PYXKK
    • 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. 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.
    • Late homework will be docked 10% per day, until a week has passed. After a week, solutions will be posted, and no homework will be accepted. There are no official "late days," but we will be reasonable about extensions, with the understanding that no homework can be accepted after solutions are posted. Please contact Mary at marykw in case of extenuating circumstances.

    Project info

    • Here is some more information about the project, which you will work on in small groups.
    • Project Proposal due 11:59pm Friday 2/11, on Gradescope.
    • Project Write-up due 11:59pm Friday 3/11, on Gradescope. (The last day of classes).
    • Project Presentations will take place during Week 10. More information about the format for the presentations will be posted later.

    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.

    Logistics

    Other course logistics

    • There are two grading schemes, you can choose which you prefer.
      • Grading scheme 1: Participation counts. 30% project, 60% HW, 10% Participation. Your participation grade is based only on attendance; you will get full points if you attend all but three classes. Each class that you skip after that (for any reason, even good reasons) will be evenly weighted to make up the total 10%. If you plan to miss many classes (for any reason, even good reasons), you may wish to opt for grading scheme 2.
        UPDATE: Now that we are back in person, "I am in quarantine" is an overwhelmingly good reason to skip class, even better than a "good reason." If you are in this situation, we can make an exception: please reach out to Mary if that is the case.
      • Grading scheme 2: Participation doesn't count. 30% project, 70% HW.
      By default you'll be on grading scheme 1, but if you'd like to opt out of a participation-based grade, you can do that at any time before the end of the quarter by contacting Mary. In both grading schemes, the three homeworks are weighted equally (even if they may be out of a different number of points).
    • 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 (and/or 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. We are happy to chat with you about as much extra work as you want to do!
    • 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. Please do not Google for solutions to HW problems.)

    Accommodations and flexibility

    If you are in a situation that makes the format of this class especially difficult for you, please reach out. We will do everything we can to make sure that the course works 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 marykw at stanford.edu.

    Class-by-class Schedule and Resources

    Below, find class-by-class resources, including videos, lecture notes, other readings, and notes about due dates.

    All videos can be found here. Note that in-class sessions are not recorded.

    Classes that have not happened yet may have broken links and are subject to change.

    Monday 1/3. 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/5. 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/10. 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:
      • Lecture Notes
      • (Optional) Essential Coding Theory, 1.6, 4.1, 4.2.
    • In-Class problems
    • In-Class solutions

    Wednesday 1/12. 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

    Monday 1/17.

    • No Class (MLK Day)

    Wednesday 1/19. 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/24. 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/26. 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

    Monday 1/31. 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/2. 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/7. Class 10: List Decoding; List-decoding capacity thm and Johnson Bound.

    Wednesday 2/9. 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/14. 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

    Wednesday 2/16. 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

    Monday 2/21.

    • No class (President's Day)

    Wednesday 2/23. 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 2/28. 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/2. 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 will give a research talk about this paper, which builds on the regenerating codes approach.

    Monday 3/7. Class 17: Project presentations

    • Project presentations. (Format TBD)

    Wednesday 3/9. Class 18: Project presentations

    • Project presentations. (Format TBD)