Error correcting codes
General information
Course Number: CS 760
(Official) Title: Topics in Computational Complexity
Instructor : Mrinal Kumar
Email : first name AT cse DOT iitb DOT ac DOT in
Office hours : Tue/Fri 5:30 pm - 6:30 pm
Logistics
The course will be taught online, with a combination of recorded lectures and notes, and office hours every week online. If you have logistic constraints which make this difficult, please send me an email, and we can try to figure a way around this. The announcements will usually be via the Moodle page of the course.
Grading
Grades will be based on problem sets and a course project/final exam. The details of the course project will be up on Moodle soon.
Prerequisites
Mathematical maturity, familiarity with the contents of a typical undergrad Discrete Math and Algorithms Class.
This is a theory course, so you should be comfortable around mathematical statements and proofs. You are NOT expected to have a background in advanced algebra for this class and the course will be self contained for the most part. The course is open to third and later year undegrads and masters and PhD students. If you aren't from one of these sets and would like to attend, feel free to drop me an email.
Description
The course is aimed as an introduction to the theory of error correcting codes and its applications in computational complexity. This theory has its roots in the works of Shannon and Hamming in the 1940's and has been a melting pot of a variety of ideas from algebra, combinatorics, probability, information theory and computer science.
A tentative list of topics can be found here.
Homeworks
Lectures
- Jan 06-08: Admin things: tentative content, grading etc.
- Jan 11-15: Basic definitions, error models. Basic algebra, linear algebra, finite fields.
- Jan 18-22: Intro to some probability. Linear Codes. Hamming bound for codes, Hamming codes.
- Jan 25-29: Gilbert-Varshamov bound.
- Feb 01-05: Singleton bound, Plotkin bound.
- Feb 08-12: Tensors and tensor rank lower bounds from rate distance tradeoffs for codes.
- Feb 15-19: Reed-Solomon codes, properties, Berlekemp-Welch decoding.
- Feb 22-26: List decoding, Johnson bound, List decoding Reed-Solomon codes.
- Feb 26-Mar 05: Midterm week, so no class this week.
- Mar 08-12: List decoding Reed-Solomon codes contd. Guruswami-Sudan's algorithm.
- Mar 15-19: List decoding up to capacity, Folded-Reed Solomon codes.
- Mar 22-26: List decoding of FRS codes with constant list size.
- Mar 29-Apr 02: Worst case to average case hardness of Permanent.
- Apr 05-09: Good codes on small alphabet: code concatenation.
- Apr 05-09: Code concatenation contd.: Forney's algorithm.
- Apr 12-16: Reed-Muller codes: properties and list decoding.
- Apr 19-20: Locally decodable codes. Summary of the course.
References