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.
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 |