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

- 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).

- 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

- 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).

- 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.