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:

• Signup for project presentations. Availability here. Email me with top three preferences.
• Potential list of projects posted. Please browse, and select your projects soon. See also Instructions on projects.
  
• 02/13/2013: Problem Set 1 released. Due date = 02/27/2013.
• Course announcement
• Grading Policy
• Important: If you wish to take this course, or are thinking about it, send mail to madhu to get added to the course mailing list.
  
• Scribe availability (Sample files for scribes: sample.tex; Uses: preamble.tex and fullpage.sty)

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.