Lecture Notes

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.

lec # TOPICS Scribe notes
  • Lecture 1 (PDF)
  • Introduction
  • Hamming Space, Distance, Code
  • Applications
Piotr Mitros (PDF)
  • Lecture 2 (PDF)
  • Shannon's Theory of Information
  • The Coding Theorem
  • Its Converse
Joungkeun Lim (PDF)
  • Lecture 3 (PDF)
  • Shannon Theory vs. Hamming Theory
  • Our Goals
  • Tools
  • Linear Codes
Adi Akavia (PDF)
  • Lecture 4 (PDF)
  • Asymptotically Good Codes
  • Projection and Volume Bound
  • Random Codes
Victor Chen (PDF)
  • 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)
  • Abstracting the RS Decoding Algorithm
  • Beyond Unique Decoding
Kunal Agrawal (PDF)
8 List Decoding of Reed-Solomon Codes Anindya Patthak (PDF)
  • 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)
  • 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