Madhu Sudan: Harvard CS 229r: Essential Coding Theory (Spring 2020)

General Info

• Lecturer: Madhu Sudan;  MD 339; email: first name at cs dot harvard dot edu; Office Hours: MW 4:30-5:30pm
• Teaching Fellow: Chi-Ning Chou: MD 138, email: chiningchou at g.harvard.edu; Office hours: TuFr 4:30pm-5:30pm (MD 1st floor common space).
• Lecture Time and Location: MW 3pm-4:15pm in Northwest B108.

Other links for the course

• Course announcement: Brief description of the course.
• Grading policy.
• Piazza site: All announcements will be routed through this site – so please sign up right away!!
• Canvas site: You will need access to Canvas to submit your problem sets.

Problem Sets

• There were 6 psets in the course + 1 (diagnostic) pset 0. Email madhu if you would like access to them for teaching your course.

Announcements

• Make sure you’ve signed up for piazza and know how to access your canvas account. If any of these is a problem, reach out to Madhu or Chi-Ning.
• Please sign up for scribing! Signup instructions and sheet here. Template for scribing here (preamble, sample.tex).

Topics, Calendar and Handouts

• Lecture 01 (Mon. 01/27): Introduction. Hamming’s Paper. Codes, Distance, Examples, Limits and Algorithms. Notes from 2008 (use these notes for technical content; not for grading policy etc.!). Reading [Chapter 1 and Chapter 2 from the text.]. Scribe notes (tex, pdf).
• Lecture 02 (Wed. 01/29): Shannon’s Theorems. Noiseless coding. Noisy Coding. Shannon Capacity. Notes from 2008. Reading [Chapter 6]. Scribe notes (tex, pdf).
• Lecture 03 (Mon. 02/03): Converse to Shannon’s theorem. Random codes. Linear codes. Gilbert-Varshamov theorems. Asymptotics of error-correcting codes. Notes from 2008. Reading [Chapter 1 and Chapter 4]. Scribe notes (tex, pdf).
• Lecture 04 (Wed. 02/05): Simple Impossibility Results for Codes. (Pigeonhole argument, packing argument, geometric arguments). Reading [Chapter 4 and Chapter 8]. Notes from 2008, Scribe notes (tex, pdf).
• Lecture 05 (Mon. 02/10): Bounds on codes continued: List-decoding, Elias-Bassalygo bound. Musing on bounds. Reed-Solomon codes. (Notes from 2008). Readings [Chapter 8, Chapter 5]. Scribe notes (tex, pdf).
• Lecture 06 (Wed. 02/12): Algebra review. Reed-Solomon Codes. Extension fields. Wozencraft ensemble. Notes from 2008 (Reed-Muller etc., BCH). Scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).
• Monday 02/17: Presidents’ Day Holiday
• Lecture 07 (Wed. 02/19): Concatenated codes. Justesen codes. Mutltvariate polynomials. Reed-Muller codes. Notes from 2013. Scribe notes (tex, pdf).
• Lecture 08 (Mon. 02/24): Reed-Muller codes – some choices of parameters. Hadamard codes, Hamming codes. BCH codes. Scribe notes (tex, pdf).
• Lecture 09 (Wed. 02/26): Algebraic Geometry Codes. Decoding Reed-Solomon Codes. Reading materials.
  • Some of the old papers on the decoding algorithm are very interesting to read. The actual history of the simple algorithm is not easy to determine. Here are some relevant links. The Peterson paper.  The Welch-Berlekamp patent. Paper with P. Gemmell (see Appendix A). Preprint of Ruud Pellikaan. Paper by Duursma and Kotter.
  • Actual reading: Chapter 13 of the text. Notes from 2008.
  • Scribe notes (tex, pdf).
• Lecture 10 (Mon. 03/02): Reed-Solomon decoding (contd.). Reed-Solomon list-decoding. Scribe notes (tex, pdf).
• Lecture 11 (Wed. 03/04): Decoding concatenated codes. List-decoding to capacity – the question. Scribe notes (tex, pdf).
• Lecture 12 (Mon. 03/09): Folded Reed-Solomon Codes and List-decoding. Notes. Additional Notes. Scribe notes (tex, pdf).
• Lecture 13 (Wed. 03/11): Graph-theoretic codes (Sipser-Spielman codes). Linear time encoding and decoding. Notes from 2008. No scribe notes this time, but here are notes from previous years (tex, pdf).
• Sat. 3/14- Sun 3/22: Spring break
• Lecture 14 (Mon. 03/23): Graph-theoretic codes I (Spielman codes). My notes. Scribe notes (tex, pdf).
• Lecture 15 (Wed. 03/25): Graph-theoretic codes II (Alon-Luby construction, Guruswami-Indyk). Notes. Scribe notes (tex, pdf).
• Lecture 16 (Mon. 03/30): Polar codes. Introduction to the notion. My notes. (See also Chapter  11 from book). Scribe notes (tex, pdf).
• Lecture 17 (Wed. 04/01): Polar codes (contd): Polarization Theorem + Algorithmic Efficiency. My notes. Scribe notes (tex, pdf).
• Lecture 18 (Mon. 04/06): Polar codes (contd): Proof of Polarization theorem. My notes. Scribe notes (tex, pdf).
• Lecture 19 (Wed. 04/08): Locality in coding: Definitions of LRCs, LDCs, LTCs. Locally Recoverable Codes. My notes. Scribe notes (tex, pdf).
• Lecture 20 (Mon. 04/13): Locality in Coding: Reed-Muller Codes and Locality. My notes. Scribe notes (tex, pdf).
• Lecture 21 (Wed. 04/15): Locality in Coding: Multiplicity Codes and KMRS Codes. My notes. Scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).
• Lecture 22 (Mon. 04/20): Codes and derandomization: Limited independence, epsilon-bias, almost independence. My notes. Scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).
• Lecture 23 (Wed. 04/22): Coding in Complexity: Hardcore predicates and Worst-case to average-case reductions. My notes. Scribe notes (tex, pdf).
• Lecture 24 (Mon. 04/27): Interactive Coding. My notes. Scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).
• Lecture 25 (Wed. 04/29): Coding for editing errors. Course wrap-up. My notes and slides. Scribe notes (tex, pdf).

Reference Materials

• Link to a draft of a textbook (with Venkatesan Guruswami and Atri Rudra).
• Previous incarnations of this course: Fall 2001, Fall 2002, Fall 2004, Spring 2008, Spring 2013. Spring 2017.
• Links to other courses on coding theory: Coming Soon.