DENIF – Documents d’Enseignement Numériques en Informatique Fondamentale

   Slides

•   Lecture 1 : Introduction
•   Lecture 2 : Basic codes and constructions
•   Lecture 3 : Algebraic Geometry Codes
•   Lecture 4 : Limits on Performance of Codes
•   Lecture 5 : Algebraic (unique) decoding
•   Lecture 6 : Algebraic (list) decoding
•   Lecture 7 : Linear time decoding
•   Lecture 8 : Decoding from random errors and erasures
•   Lecture 9 : Applications in complexity theory
•   Lecture 10 : Complexity results in coding theory

   Slides

•   1. Introduction. Hamming space, distance, code. Applications.
•   2. Shannon's theory of information. The coding theorem. Its converse.
•   3. Shannon theory vs. Hamming theory. Our goals. Linear codes.
•   4. Singleton bound. Polynomials over finite fields. Reed Solomon codes. Reed-Muller codes. Hadamard codes (again!).
•   5. Asymptotically good codes. Random codes.
•   6. Concatenated codes. Forney codes. Justesen codes.
•   7. Algebraic geometry codes.
•   8. Impossibility results for codes.
•   9. Elias-Bassalygo-Johnson bounds. MacWilliams Identities. Linear Programming bound.
•   10. Algorithmic questions: Encoding. Decoding. Decoding RS codes.
•   11. Decoding RS codes, AG codes.
•   12. Decoding AG codes (contd.), Decoding concatenated codes. (no slides)
•   13. List decoding of Reed-Solomon Codes. (no slides)
•   14. Locally decodable codes. Local unambiguous decoding of some Hadamard codes and Reed-Muller codes.
•   15. Local (list) decoding of Reed-Muller codes.
•   16. Linear time decoding: LDPC codes, Sipser-Spielman codes.
•   17. Linear time encoding and decoding: Spielman codes.
•   18. Linear time + near optimal error decoding!
•   19. Expander based constructions of efficiently decodable codes.
•   20. Some NP-hard coding theoretic problems.
•   21. Applications in Complexity theory - 1. (no slides).
•   22. Applications in Complexity theory - 2 : Randomness and derandomization; Randomness extractors; Trevisan's extractors.
•   23. Applications in Complexity theory - 3.

   Draft of course notes

•   Lecture 1
•   Lecture 2
•   Lecture 3
•   Lecture 4
•   Lecture 5
•   Lecture 6
•   Lecture 7
•   Lecture 8
•   Lecture 9
•   Lecture 10
•   Lecture 11
•   Lecture 12
•   Lecture 13
•   Lecture 14
•   Lecture 15
•   Lecture 16
•   Lecture 17
•   Lecture 18
•   Lecture 19
•   Lecture 20
•   Lecture 21

   Course Notes  

•   Notes of all finished lectures (1 to 15)
•   1. Introduction. Shannon's theorem. Information, Entropy.
•   2. Converse of Shannon's noisy coding theorem. Discussion on Shannon capacity. Hamming's theory. Error-correcting codes. Linear codes.
•   3. Hamming Codes. Hamming bound. Perfect codes. Finite fields. Polynomials over finite fields.
•   4. Singleton bound. Reed Solomon codes, MDS codes. Reed Muller codes, Hadamard codes.
•   4,5. BCH Codes.
•   5. Asymptotically good codes over small alphabets. Random codes, Random linear codes, Wozencraft ensemble.
•   6. Wozencraft ensemble (contd.). Operations on codes. Concatenated codes. Forney codes. Justesen codes.
•   7. Algebraic geometry codes: Codes better than random codes.
•   8. Impossibility results for codes: Plotkin bound, Johnson bound, Elias-Bassalygo bound.
•   9. Bounds (contd.): MacWilliams Identities. Linear Programming bound. The asymptotic perspective.
•   10. Algorithmic questions: Encoding. Decoding. Decoding from erasures. Decoding RS codes.
•   11. Abstract algorithm for decoding. Application: AG codes. Concatenated codes & GMD decoding.
•   12. List decoding: Recall combinatorics. List decoding of RS codes.
•   13. Improvements to list decoding.
•   14. Abstract decoding. Decoding CRT codes.
•   15. Implicit decoding. List decoding of Reed-Muller codes.
•   16. Linear time decoding: LDPC codes, Sipser-Spielman codes.
•   17. Linear time encoding and decoding: Spielman codes.
•   18. Linear time + near optimal error decoding!
•   19. Guest Lecturer: Piotr Indyk Expander based constructions of efficiently decodable codes
•   20. Some NP-hard coding theoretic problems.
•   21. Applications in Complexity theory - 1.
•   22. Applications in Complexity theory - 2.
•   23. Applications in Complexity theory - 3.
•   References