Calendar

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