Accueil
Connexion
DENIF –
Documents d’Enseignement Numériques en Informatique Fondamentale
Thèmes
Cursus
Enseignants
Essential Coding Theory
Thème :
Cryptographie
–
Cursus :
MIT
2002 - Essential Coding Theory
Same references as previous year.
Slides
Madhu Sudan
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.