Topics in error correcting codes
General information
Course Number: CSS 418.1
Title: Topics in error correcting codes
Lectures: Tue/Thu 11:30 AM-1 PM
Instructor : Mrinal Kumar
Email : first name AT tifr DOT res DOT in
Office hours : Mon 4:00 pm - 5:00 pm
Grading
Grades will be based on problem sets (50%), a class project (40%) and class participation (10%).
Prerequisites
Mathematical maturity, familiarity with the contents of a typical Discrete Math and Algorithms Class and comfort with reading and writing proofs.
This is a theory course, so you should be comfortable around mathematical statements and proofs.
You are NOT expected to have a background in coding theory for this class and the course will be self contained for the most part.
Description
The course is aimed at studying some advanced topics in the theory of error correcting codes and some applications in computational complexity. For a large part, we will focus on the notion of locality in coding theory and will study the notions of local decoding, local testing and local correction in coding theory. We will also see applications of some of these ideas to problems like private information retrieval and to problems in pseudorandomness.
A tentative list of topics can be found here.
Homeworks
- Problem set - 1 due on October 1st.
Lectures
- Aug 26: Admin things: tentative content, grading etc. Intro to codes.
- Aug 28: Reed-Solomon codes - definitions, properties, Berlekemp-Welch decoder, list decoding.
- Sep 02: Reed-Solomon codes contd. - Sudan's algorithm, Guruswami-Sudan's algorithm.
- Sep 04: Univariate multiplicity codes - list decoding up to capacity, pruning the list size.
- Sep 09: Local decoding and correction - definition, local correction of Hadamard and Reed-Muller codes.
- Sep 11: Local correction with high rate - multivariate multiplicity codes.
- Sep 16: Multivariate multiplicity codes contd. Matching vector codes.
- Sep 18: Matching vector codes contd.
- Sep 23: Matching vector codes contd., Matching vector families.
- Sep 25: Private information retrieval.
- Sep 30: Private information retrieval contd. Lower bounds for LDCs.
- Oct 02: No class (Gandhi Jayanti).
- Oct 07: Lower bounds for LDCs contd: Katz-Trevisan.
- Oct 09: No class (Seminar talk).
- Oct 11: Lower bounds for 2 query linear LDCs: Goldreich-Karloff-Schulman-Trevisan (Extra lecture).
- Oct 16: Lower bounds for 3 query linear LCCs: Alrabiah-Guruswami.
- Oct 21: BLR Linearity test.
- Oct 23: Low degree test - Polischuk-Spielman.
- Oct 28: Low degree test - Polischuk-Spielman contd.
- Oct 30: Low degree test - Friedl-Sudan.
- Nov 04: Low degree test - Friedl-Sudan contd.
- Nov 06: Low degree test in high error regime - Arora-Sudan.
- Nov 11: Low degree test in high error regime - Arora-Sudan contd.
- Nov 13: Low degree test via a planes test.
- Nov 18: Low degree test via a planes test contd.
References