This section contains a set of lecture notes and scribe notes for each lecture. Scribe notes are latex transcriptions by students as part of class work. Scribe notes are used with permission of the students named.
Lecture files| 1 | - Lecture 1 (PDF)
- Introduction
- Hamming Space, Distance, Code
- Applications
| Piotr Mitros (PDF) |
| 2 | - Lecture 2 (PDF)
- Shannon's Theory of Information
- The Coding Theorem
- Its Converse
| Joungkeun Lim (PDF) |
| 3 | - Lecture 3 (PDF)
- Shannon Theory vs. Hamming Theory
- Our Goals
- Tools
- Linear Codes
| Adi Akavia (PDF) |
| 4 | - Lecture 4 (PDF)
- Asymptotically Good Codes
- Projection and Volume Bound
- Random Codes
| Victor Chen (PDF) |
| 5 | - Lecture 5 (PDF)
- Algebraic Codes: Reed-Solomon, Reed-Muller, Hadamard
- Plotkin Bound
| Swastik Kopparty (PDF) |
| 6 | Decoding Reed-Solomon Codes - The Welch-Berlekamp Algorithm | Kyomin Jung (PDF) |
| 7 | - Abstracting the RS Decoding Algorithm
- Beyond Unique Decoding
| Kunal Agrawal (PDF) |
| 8 | List Decoding of Reed-Solomon Codes | Anindya Patthak (PDF) |
| 9 | - Concatenated Codes and Decoding
- Justesen Codes
| Jesse Kamp (PDF) |
| 10 | Achieving Shannon Capacity in Polytime with Concatenated Codes | Elena Grigorescu (PDF) |
| 11 | List Decoding versus Rate versus Distance | Anastasios Sidiropoulos (PDF) |
| 12 | The Gap between Constructive and Existential Results in Coding Theory | Kevin Matulef (PDF) |
| 13 | Algebraic Geometry Codes | Alexey Spiridonov (PDF) |
| 14 | Linear-time Decodable Codes | Vinod Vaikuntanathan (PDF) |
| 15 | Linear-time Encodable and Decodable Codes | Reina Riemann (PDF) |
| 16 | - Spielman Codes and Decoding
- Correcting Random Error in Linear Time, Expander Codes (Type II)
| Abhinav Kumar (PDF) |
| 17 | Expander Codes - the ABNNR Construction | Venkat Chandar (PDF) |
| 18 | Computation and Randomness: Pseudo-randomness, Limited Independence, Small-bias Spaces | Kyomin Jung (PDF) |
| 19 | Extraction of Randomness, Min-entropy, Statistical Difference, Extractors and Codes | Anup Rao (PDF) |
| 20 | Trevisan's Extractor | |
| 21 | Ta-Shma-Zuckerman-Safra Extractor, Guruswami-codes | Paul Valiant (PDF) |
| 22 | Ta-Shma-Zuckerman-Safra Extractor (cont.) | Swastik Kopparty (PDF) |
| 23 | Expanders, Eigenvalues and the Zig-Zag Product | Victor Chen (PDF) |
| 24 | TBA | |
| 25 | TBA | |