| lec # | TOPICS | KEY DATES |
|---|---|---|
| 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 |
