Essential Coding Theory (MIT 6.440)

General Info:
  • Lecturer: Madhu Sudan;  32-G640; email: first name at mit dot edu
  • TA: None. Voluntary help welcome.
  • Units: 3-0-9 H Level Grad Credit.
  • Time and Location: MW 11-12:30 in 26-204 (Changed on 2/4/2013)
Announcements:

Tentative schedule of topics: (Lowlighted links point to notes from previous offering)

  • Lecture 01 (Wed. 02/06): Introduction. Hamming's Paper: Distance, Codes. Notes, Scribe notes (tex, pdf).
  • Lecture 02 (Mon. 02/11): Shannon's Theorem. Shannon capacity.  Notes, Scribe notes (tex, pdf).
  • Lecture 03 (Wed. 02/13): Converse to Shannon's theorem. Random codes. Linear codes. Gilbert-Varshamov theorems. Asymptotics of error-correcting codes. Notes, Scribe notes (tex, pdf).
  • Monday (02/18):  President's Day holiday.
  • Lecture 04 (Tue. 02/19): MIT Virtual Monday! Simple impossibility results for codes. {Singleton, Hamming, Plotkin, Elias-Bassalygo, Johnson} bounds. Notes. Scribe notes (tex, pdf).
  • Lecture 05 (Wed. 02/20): Finish Elias-Bassalygo and Johnson bounds. Start algebraic codes: Finite fields, Polynomials over fields. Notes. Scribe notes (tex, pdf). 
  • Lecture 06 (Mon. 02/25): Algebraic codes: Reed-Solomon codes, Reed-Muller codes, Hadamard codes. Notes. Scribe notes (tex, pdf).
  • Lecture 07 (Wed. 02/27): Binary codes by algebraic techniques: Concatenated (Forney) codes, Justesen codes, BCH codes. Notes. Scribe notes (tex, pdf).
  • Lecture 08 (Mon. 03/04): Algebraic geometry codes (the idea without proofs). Notes. Scribe notes (tex, pdf).
  • Lecture 09 (Wed. 03/06): Guest Lecture by Prof. Eli Ben-Sasson: Limits to list-decodability of Reed-Solomon Codes. Scribe notes (tex, pdf).
  • Lecture 10 (Mon. 03/11): Algorithmic problems; Decoding Reed-Solomon Codes; Abstraction. Notes. Scribe notes (tex, pdf).
  • Lecture 11 (Wed. 03/13): Decoding Concatenated Codes. Notes. Scribe notes (tex, pdf).
  • Lecture 12 (Mon. 03/18): List-decoding. List-decoding radius. Vs. Distance. Vs. Rate. List-decoding RS codes. Notes. Scribe notes (tex, pdf).
  • Lecture 13 (Wed. 03/20): List-decoding of Folded Reed-Solomon Codes. Scribe notes (tex, pdf).
  • (03/25-03/29): Spring Break
  • Lecture 14 (Mon. 04/01): Graph-theoretic Codes (Gallager, Tanner, Sipser-Spielman). Notes. Scribe notes (tex, pdf).
  • Lecture 15 (Wed. 04/03): Decoding Sipser-Spielman Codes. Linear-time encodable and decodable codes. Notes. Scribe notes (tex, pdf).
  • Lecture 16 (Mon. 04/08): Linear-time encodable and decodable codes. Irregular LDPC codes. Notes. Scribe notes (tex, pdf).
  • Lecture 17 (Wed. 04/10): Polar codes - I.
  • (Mon. 04/15 + Tue. 04/16): Patriots Day holiday.
  • Lecture 18 (Wed. 04/17): Polar codes - II. Scribe notes (tex, pdf).
  • Lecture 19 (Mon 04/22): Codes from other codes. Scribe notes (tex, pdf).
  • Lecture 20 (Wed. 04/24): TBD.
  • Lecture 21 (Mon. 04/29): Codes and Computatinal Complexity: Complexity of Coding Problems. Scribe notes (tex, pdf).
  • Lecture 22 (Wed. 05/01): Codes and Computational Complexity: Elementary pseudorandomness. Notes.
  • Lecture 23 (Mon. 05/06):  Codes and Computational Complexity - III
  • Project Presentations: Day 1 (Time TBD).
  • Wednesday (05/08):  No lecture due to project presentations.
  • Project Presentations: Day 2 (Time TBD).
  • Lecture 24 (Mon. 05/13):  Codes and Computational Complexity - IV
  • Wednesday (05/15):  No lecture.

References:

  • Draft of a book with Guruswami and Rudra. 
  • Other references to come soon.