Fall 2019: Coding Theory for Theoretical Computer Science

The aim of this course is to provide an introduction to coding theory from a theoretical computer science perspective, and showcase the fascinating interplay between the twotopics. A tentative list of topics to be covered includes: basics of codes, linear codes, fundamental bounds on codes, composition of codes, algebraic codes, combinatorial and algorithmic list decoding, applications to cryptography and learning theory, locallytestable and locally decodable codes, expander graphs and graph-based codes, hardness and randomness, list recovery and soft decision, randomness extractors, sparse signal processing and sparse transforms.