Madhu Sudan: Essential Coding Theory
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.
- 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)
Course announcement
Prereq: 6.006, 6.045.
Time: MW 11-12:30
Location: 26-204 [NOTE THE CHANGE as of 2/4/2013]
3-0-9 H-Level Grad Credit
Homepage: http://people.csail.mit.edu/madhu/ST13/
Introduces essential elements the theory of error-correcting codes. Focuses on the basic results in the area, taught from first principles. Special focus will be given on results of asymptotic or algorithmic significance. Principal topics include
- Construction and existence results for error-correcting codes;
- Limitations on the combinatorial performance of error-correcting codes;
- Decoding algorithms
- Applications to other areas of mathematics and computer science.
Lecture notes for this course from previous offerings give further details on the material covered. These may be found at http://people.csail.mit.edu/madhu/FT01.
Instructor: Madhu Sudan
Grading Policy
Grading Policy for Essential Coding Theory (MIT 6.440):
Grades will be based on a combination of the following ingredients
- 2-4 Problem Sets.
- A course project (instructions to be posted shortly).
- Class Participation (biased towards the second half of the term).
- Additionally, you must scribe at least one lecture.
Tentative schedule of topics
(Bold font indicates 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.