Course Announcement: CSS.318.1: Coding Theory - Winter/Summer Semester (2023-24)

Time: Tues 11:30-13:00 and 14:00-15:30
Location: A201
Instructors: and
Homepage: https://www.tcs.tifr.res.in/~prahladh/teaching/2023-24/coding/

CSS.318.1: Coding Theory

Error-correcting codes form the backbone of today's communication as they help us communicate in the presence of noise (both random and adversarial).

Can You hear me now?

The course introduces the essentials of error-correcting codes, with a focus on algorithmic results. We will begin with the basics, study basic possibility and impossibility results and proceed to recent and advanced topics in coding theory. The topics covered in the course will include

Coding theory fundamentals (adversarial vs random errors aka Shannon vs Hamming models)
Bounds: What can be done and what cannot be done
Algorithmic issues: encoding, decoding, testing
Reed Solomon codes and other polynomial codes
Expander Codes
List-decoding
Polar Codes
Application to other areas of computer science, combinatorics and mathematics.
...

Earlier versions of this course were offered in the Monsoon 2022 and Monsoon 2016 semesters. This edition of the course will be a slight variant of the Monsoon 2022 offering.

Grading

Students taking the course for credit will be expected to:

Do problem sets (approx 1 pset every 2-3 weeks)
Project / Paper Presentation / Final Exam
Participate actively in class
Grading Policy:
- Problems Sets - 72% (best n-1 of n psets will contribute towards grade)
- A total of 14 days extra-time that can be distributed across psets
- Class Participation - 8%
- Project / Paper Presentation / Final Exam -- 20%

References

[GRS15]	Venkatesan Guruswami, Atri Rudra and Madhu Sudan, "Essential Coding Theory", (draft of book), 2022.
[Gur14]	Venkatesan Guruswami, "15-859Y: Coding Theory", CMU, Fall 2014.
[Har16]	Prahladh Harsha, "A mini course on Coding Theory - An Algorithmic Viewpoint", TIFR, August 2016.
[Kop16]	Swastik Kopparty, "198:540: Error Correcting Codes", Rutgers, Spring 2016.
[RU08]	Tom Richardson and Rüdiger Urbanke, "Modern Coding Theory", Cambridge University Press, 2008.
[Sud01]	Madhu Sudan, "6.897: Algorithmic Introduction to Coding Theory ", MIT, Fall 2001.
[Sud13]	Madhu Sudan, "6.440: Essential Coding Theory", MIT, Spring 2013.

This page has been accessed at least times since 15 Jan, 2024.

Prahladh Harsha