Coding Theory (Spring 2009)

Lecturer: Irit Dinur
Location: Ziskind 1
Time: Thursdays 9:00 - 11:00


Syllabus (preliminary): This course will focus on coding theory and its applications to theoretical computer science. Topics include: Codes, Linear Codes, Singleton bound, Reed-Solomon codes, Reed-Muller codes, Random codes, Justesen codes, Algebraic geometric codes, Johnson bounds, efficient decoding and encoding, list decoding, capacity-achieving list-decodable codes, NP-hardness of coding questions, applications to extractors and derandomization.

Requirements: Attendance, homework assignments (once every two weeks).

Prerequisites: Mathematical maturity is important for this class. In addition, familiarity with the basics of probability, probabilistic method, algebra (especially finite fields), analysis of algorithms, and computational complexity would be helpful.

Exercises:

Problem Set #1: due April 7, 2009.

Problem Set #2: due May 14, 2009.

Problem Set #3: due July 9, 2009.

Date Topic
March 19 Introduction: Basic definitions, Hamming code, Hadamard Code.
March 26 Singleton bound. Reed-Solomon Codes. Volume (Hamming) Bound. Gilbert-Varshamov Bound.
April 2 Concatenatenation of codes. Zyablov Bound. Justesen Codes.
April 16 Wozencraft's ensemble. Decoding Reed-Solomon Codes.
April 23 Decoding concatenated codes (with outer RS code).
April 30 no class
May 7 LDPC codes
May 14 Expanders & codes
Online courses: