Prereq: CS 121/124/125 or equivalents + Mathematical Maturity. Undergraduates interested in the course must write to Madhu explaining (1) Why they are taking this course and (2) what their math + CS theory prep is.
Time: MW 11:15-12:30
Location: SEC LL2.224 (in Allston)
Homepage: http://madhu.seas.harvard.edu/courses/Fall2022/
Information Theory originated in the seminal work of Shannon (1948) that attempted to formalize and quantify communication. This theory was mostly ignored by theoretical computer science till the 1990s when tools and concepts from Information Theory started to play a central role in powerful results in the field. Notable examples include the Parallel Repetition Theorem of Raz (1994), the development of the Information Complexity measure as a means of understanding Communication Complexity (2001). Today Information Theoretic measures and tools influence many aspects of CS theory including analysis of streaming algorithms, differential privacy and game theory.
This course will introduce the basic concepts in information theory and then sample topics of interest to CS theory where information theoretic tools play a central role. See http://madhu.seas.harvard.edu/courses/Fall2022 for more information.
If you are interested (even tentatively) in the course, add the course to your Crimson cart and following the discussion forum on Ed (accessible via canvas).
Instructor: Madhu Sudan
TFs: Chi-Ning Chou, Ratip Emin Berker