| 1 | - Introduction
- Hamming Space, Distance, Code
- Applications
| Problem set 1 out |
| 2 | - Shannon's Theory of Information
- The Coding Theorem
- Its Converse
| |
| 3 | - Shannon Theory vs. Hamming Theory
- Our Goals
- Tools
- Linear Codes
| Problem set 1, part I due |
| 4 | - Asymptotically Good Codes
- Projection and Volume Bound
- Random Codes
| |
| 5 | - Algebraic Codes: Reed-Solomon, Reed-Muller, Hadamard
- Plotkin Bound
| Problem set 1, part II due |
| 6 | Decoding Reed-Solomon Codes - The Welch-Berlekamp Algorithm | |
| 7 | - Abstracting the RS Decoding Algorithm
- Beyond Unique Decoding
| |
| 8 | List Decoding of Reed-Solomon Codes | Problem set 2 out |
| 9 | - Concatenated Codes and Decoding
- Justesen Codes
| Problem set 2 due |
| 10 | Achieving Shannon Capacity in Polytime with Concatenated Codes | |
| 11 | List Decoding versus Rate versus Distance | |
| 12 | The Gap between Constructive and Existential Results in Coding Theory | |
| 13 | Algebraic Geometry Codes | |
| 14 | Linear-time Decodable Codes | |
| 15 | Linear-time Encodable and Decodable Codes | |
| 16 | - Spielman Codes and Decoding
- Correcting Random Error in Linear Time, Expander Codes (Type II)
| |
| 17 | Expander Codes - the ABNNR Construction | |
| 18 | Computation and Randomness: Pseudo-randomness, Limited Independence, Small-bias Spaces | |
| 19 | Extraction of Randomness, Min-entropy, Statistical Difference, Extractors and Codes | |
| 20 | Trevisan's Extractor | |
| 21 | Ta-Shma-Zuckerman-Safra Extractor, Guruswami-codes | |
| 22 | Ta-Shma-Zuckerman-Safra Extractor (cont.) | |
| 23 | Expanders, Eigenvalues and the Zig-Zag Product | |
| 24 | TBA | |
| 25 | TBA | |