Harvard University homepage
HARVARD.EDU

Madhu Sudan: Essential Coding Theory

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

Project Topics

Potential Project Topics for Essential Coding Theory (MIT 6.440):

  1. A Mathematical Theory of Communication (by Claude Shannon). Project unassigned.
  2. Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes (by Tao Jiang and Alexander Vardy).
    Improving the Gilbert-Varshamov bounds for q-ary codes (by Van Vu and Lei Wu). Project unassigned.
  3. Long Nonbinary Codes Exceeding the Gilbert – Varshamov Bound for any Fixed Distance (by Sergey Yekhanin and Ilya Dumer). Project unassigned.
  4. Generalized Alon-Boppana Theorems and Error-Correcting Codes (by Joel Friedman and Jean-Pierre Tillich).
    Linear programming bounds for codes via a covering argument (by Michael Navon and Alex Samorodnitsky). Project assigned (Ankur + Aleksander).
  5. A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound (by A. Garcia and H. Stichtenoth). Project unassigned.
  6. Combinatorial Bounds for List Decoding (by V. Guruswami, J. Hastad, M. Sudan and D. Zuckerman).
    Limits to list decodability of linear codes (by V. Guruswami). Project assigned (Minji + Daniel + Shirley).
  7. Subspace Polynomials and List Decoding of Reed-Solomon Codes (by E. Ben-Sasson, S. Kopparty and J. Radhakrishnan). Project assigned (Minji + Daniel + Shirley).
  8. Limits to List Decoding Reed-Solomon Codes (by V. Guruswami and A. Rudra). Project unassigned.
  9. Maximum-Likelihood Decoding of Reed-Solomon Codes is NP-hard (by V. Guruswami and A. Vardy). Project unassigned.
  10. Hardness of approximating the closest vector problem with pre-processing (by Michael Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth Vishnoi). Project unassigned.
  11. Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes (by Michael Alekhnovich). Project half-assigned (Huy + ?).
  12. Pseudorandom generators without the XOR lemma (by M. Sudan, L. Trevisan, and S. Vadhan). Project assigned (Shira + Yinmeng).
  13. Extractors and Pseudorandom Generators (by L. Trevisan). Project assigned (Shubhangi + Jelani).
  14. Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes (by Venkatesan Guruswami, Christopher Umans, and Salil Vadhan). Project unassigned.
  15. When Hamming Meets Euclid: the Approximability of Geometric TSP and MST (by Luca Trevisan). Project unassigned.
  16. Towards 3-Query Locally Decodable Codes of Subexponential Length (by Sergey Yekhanin). Project unassigned.
Course announcement

Prereq: 6.006, 6.045.
Time: MW 1-2:30
Location: 26-322
3-0-9 H-Level Grad Credit
Homepage: http://people.csail.mit.edu/madhu/ST08/ 

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
TA: Swastik Kopparty

Grading Policy

Grades will be based on a combination of the following ingredient

  1. 2-4 Problem Sets.
  2. A course project (instructions to be posted shortly).
  3. Class Participation (biased towards the second half of the term).
  4. Additionally, you must scribe at least one lecture.

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

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.