Topics in Error Correcting Codes

General Information

Instructor: Adi Akavia
Time: Tuesdays 3:20-6:20 PM
Location: Hill 250
Course number: Mathematics 16:642:612:01 (index 49822)

Computer Science 16:198:672:01 (index 43238)

Prerequisites: The course assumes comfort with analysis of algorithms, basic linear algebra and elementary probability

Course Description

Error correcting codes (ECCs) encode messages in a redundant way to allow recovery of the original message even in the presence of noise. Error correcting codes were originally designed for communication over noisy channels or storage in noisy devices, and have since found applications also in theoretical computer science. In this course we study ECC focusing on asymptotic bounds, efficient algorithms and applications in theoretical computer science. Results will be taught from first principals.

Announcements

Problem set 1 is available, due Feb 13, 2009
Problem set 2 is available, due April 14, 2009

Tentative list of topics
(subject to changes due to time constraints and class interests)

· Basic definitions (codes as combinatorial objects, algorithmic problems in coding theory)

· Shannon coding theorem on channel capacity

· Combinatorial lower bounds on parameters achievable by error correcting codes

· Randomized constructions of good codes (existence results)

· Explicit codes constructions (Reed-Solomon codes, Reed-Muller codes, LDPC and expander based codes, Hadamard codes, Homomorphism codes, Multiplication codes)

· Code operators (puncturing, concatenation, Boolean-ization)

· Efficient algorithms for unique decoding and list decoding

· Local algorithms for decoding, testing and self correcting

· Relations to cryptography and complexity (secret sharing, proving hard-core predicates, hardness amplification, pseudo-randomness)

Detailed Schedule

Disclaimer: Notes marked as “Draft” were not reviewed by me yet.
Lecture 1 (Jan 20): Introduction, basic definitions, Hamming code. Scribe: Geetha Jagannathan; draft of notes.

Lecture 2 (Jan 21): Hadamard codes, existence of good codes. Scribe: Fengmin Wang; draft of notes.

Lecture 3 (Jan 27): Shannon coding theorem, lower/upper bounds (Gilbert-Varashamov, Singleton, Plotkin, Johnson, Elias-Bassalygo). Scribe: Darakhshan Mir; draft of notes.

Lecture 4 (Feb 3): Reed-Solomon codes and Shamir secret sharing scheme. Scribe: Luke Friedman; draft of notes.
Lecture 5 (Feb 10): Reed-Solomon codes and concatenated codes – information theoretic aspects. Scribe: Dev Desai; draft of notes
Lecture 6 (Feb 17): Reed-Solomon codes and concatenated codes – algorithmic aspects (in unique decoding realm). Scribe: Mangesh Gupte; draft of notes
Lecture 7 (Feb 24): Gallagers Low Density Parity Check Codes. Scribe: Geetha Jagannathan;
Lecture 8 (Mar 3): Expander based codes: Sipser Spielman codes (parameters and decoding), ABNNR codes (parameters). Scribe: Rajat Mittal; draft of notes
Lecture 9 (Mar 10): Guruswami-Indyk’s Unique decoding of ABNNR codes, Akavia-Venkatesan’s Soft local decoding of concatenated ABNNR codes, Guruswami-Gopalan Deterministic hardness amplification in NP. Scribe: Pavel Mahmud
Lecture 10 (March 24): Goldreich Levin hardcore predicate and Hadamard codes local list decoding
Lecture 11 (March 31): No class due to DIMACS Property Testing Workshop
Lecture 12 (April 7): Goldreich-Levin and Akavia-Goldwasser-Safra Learning heavy Fourier coefficients
Lecture 13 (April 14): Akavia-Goldwasser-Safra proving hard-core predicates via list decoding
Lecture 14 (April 21): TBD
Lecture 15 (April 28): TBD

Class Assignments and Grading

Students are expected to present one technical talk and scribe 1-2 lectures. There will be a few problem sets. There will be no exam. Grades are based on participation in class discussions and on the above.

Scribing: please submit .tex and .pdf files created using these template and style files: template.tex, scribe.sty

References

1. Madhu Sudan’s, Essential Coding Theory, lecture notes

2. Venkat Guruswami, Error-Correcting Codes: Constructions and Algorithms, lecture notes

3. Atri Rudra, Error Correcting Codes: Combinatorics, Algorithms and Applications, lecture notes

4. F.J. MacWilliams and N.J.A. Sloane: The Theory of Error-Correcting Codes, North-Holland, 1977

5. J.H. van Lint: Introduction to Coding Theory, Springer, 1982, (Third edition, 1999)

6. T. Richardson, R. Urbanke, Modern Coding Theory, available online

7. S. Hoory, N. Linial, A. Wigderson, Expander graphs and their applications, Bull. AMS, 43(2006) 439—561

8. R. G. Gallager, Low Density Parity Check Codes, Transactions of the IRE Professional Group on Information Theory, Vol. IT-8, January 1962, pp. 2l-28, available online