MIT 6.440: Essential Coding Theory (Spring 2008)

Essential Coding Theory (MIT 6.440)

General Info:

Lecturer: Madhu Sudan; 32-G640; email: first name at mit dot edu
TA: Swastik Kopparty; 32-G636; email: first name at mit dot edu; Office Hours: Wednesday, 5-7pm in 32-G631
Units: 3-0-9 H Level Grad Credit;
Time and Location: MW 1-2:30 in 26-322

Announcements:

Important: This course has a mailing list. If you haven't received mail to this list, mail madhu to get added to this list.

Please fill out the course evaluations.

Project topics
Course announcement
Grading Policy
Scribe availability (Sample files for scribes: sample.tex; Uses: preamble.tex and fullpage.sty)
Problem Set 1 (tex, pdf).
Problem Set 2 (tex, pdf).

Tentative list of Topics:

Lecture 01 (02/06): Introduction. Hamming's Paper: Distance, Codes. Notes, Scribe notes.

Lecture 02 (02/11): Shannon's Theorem. Shannon capacity. Notes, Scribe notes.

Lecture 03 (02/13): Converse to Shannon's theorem. Random codes. Linear codes. Gilbert-Varshamov theorems. Asymptotics of error-correcting codes. Notes, Scribe notes.

Monday 02/18: Presidents Day Holiday.

Lecture 04 (02/19): MIT Virtual Monday! Simple impossibility results for codes. {Singleton, Hamming, Plotkin, Elias-Bassalygo, Johnson} bounds. Notes. Scribe notes.

Lecture 05 (02/20): Algebra Notes: Finite fields, Polynomials over fields. Notes. Scribe notes.

Lecture 06 (02/25): Wozencraft ensemble, Reed-Solomon codes, Reed-Muller codes, Hadamard codes. Notes. Scribe notes.

Lecture 07 (02/27): Binary codes by algebraic techniques: Concatenated (Forney) codes, Justesen codes, BCH codes. Notes. Scribe notes.

Lecture 08 (03/03): Algebraic geometry codes (the idea without proofs). Notes. Scribe notes.

Lecture 09 (03/05): Combinatorics of error-correcting codes: Summary. Notes. Scribe notes.

Lecture 10 (03/10): Algorithmic problems; Decoding Reed-Solomon Codes; Abstraction. Notes. Scribe notes.

Lecture 11 (03/12): Decoding Concatenated Codes. Notes. Scribe notes.

Lecture 12 (03/17): List-decoding. List-decoding radius. Vs. Distance. Vs. Rate. Notes. Scribe notes.

Lecture 13 (03/19): List-decoding of Reed-Solomon Codes. Notes. Scribe notes.

03/24 - 03/28: Spring Break!

Lecture 14 (03/31): Cancelled!

Lecture 15 (04/02): Parvaresh-Vardy-Guruswami-Rudra Codes (rate-optimal list decodable codes over large alphabets). Notes. Scribe notes.

Lecture 16 (04/07): PVGR - II. Notes. Scribe notes.

Lecture 17 (04/09): Graph-theoretic codes (Gallager, Tanner). Expander codes (Sipser-Spielman). Notes. No scribe notes :-(.

Lecture 18 (04/14): Linear time decodable codes. Notes. Scribe notes.

Lecture 19 (04/16): Spielman codes: Linear-time encodability and decodability. Notes. Scribe notes.

Monday 04/21-04/22: Patriots Day Holiday.

Lecture 20 (04/23): Linear-time list-decodability (Guruswami-Indyk).

Lecture 21 (04/28): Computational complexity of decoding linear codes.

Lecture 22 (04/30): Codes in computational complexity: Secret-sharing, hardcore predicates.

Lecture 23 (05/05): Codes in computational complexity: Hardness amplification, and list-decodability of Reed-Muller codes.

Tuesday (05/06): 9am-12:30pm: Project Presentations in G631 (CANCELLED)

Wednesday (05/07): LECTURE CANCELLED Due to Project Presentations

Wednesday (05/07): 10:15am-12:30pm: Project Presentations in G531 Check availability here and sign up for a presentation slot

Lecture 24 (05/12): TBA

Lecture 25 (05/14): TBA

Related Courses:

Students should not consider Essential Coding Theory a replacement for MIT 6.451 - Principles of Digital Communication II. While both courses cover aspects of error-correcting codes, the topics are quite different (with some overlap), and the perspectives are vastly different. Students are encouraged to take both courses.

MIT 6.441 (Transmission of Information) is another course that teaches rich mathematical theory inspired by communication.

The material taught in Essential Coding Theory will have some minimal overlap with courses in computational complexity such as Advanced Complexity Theory (MIT 6.841) and Randomness and Computation (MIT 6.842).

References:

Mostly we will be following the notes from the Fall 2001 version of this course. Notes from Fall 2002 and Fall 2004 vary slightly in content and vastly in quality.

Some classical texts in Coding Theory include:

F.J. MacWilliams and N.J.A. Sloane: The Theory of Error-Correcting Codes, North-Holland, 1977.
J.H. van Lint: Introduction to Coding Theory, Springer, 1982.

Some new texts include:

R. Roth: Introduction to Coding Theory, Cambridge University Press, 2006.
J. Justesen and T. Hoholdt: A Course in Error-Correcting Codes, EMS Press, 2004.

Some other references include:

E.R. Berlekamp: Key papers in the development of Coding Theory, IEEE Press, 1974.
V. Pless and C.H. Huffman: Handbook of Coding Theory (2 volumes), North-Holland, 1998.