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