Harvard CS 229r: Information Theory for CS

General Info

Lecturer: Madhu Sudan (SEC 3.434, madhu@cs.harvard.edu ; Office Hours: TBD )

TFs:

Chi-Ning Chou (SEC 3.334, chiningchou@g.harvard.edu; Office Hours: Tue. 4:30pm-6pm @ SEC 3.317)
R. Emin Berker (SEC 5.449, rberker@college.harvard.edu; Office Hours: Wed. 8pm-10pm @ Winthrop Dining Hall)

Lecture time and Location: MW 11:15-12:30, SEC LL2.224

Google Calendar for the course.
Please sign up for scribing. See this Ed post.
Checklist:
- Put this course in your Crimson Cart for canvas access (needed for other stuff below).
- If you are an undergraduate, send email to madhu explaining (1) why you are taking the course and (2) what your math + CS theory prep is.
- Confirm Ed and Gradescope access. (Gradescope should be enabled in a few days).
- Solve PSet 0 (tex, pdf).

(08/31): Introduction. Shearer's Lemma. (My notes. Scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).)
- References for today's lecture: [CFGShearer], [Radhakrishnan]. Advanced reading [Friedgut], [EllisFKY]
- Some cool 2d projections of 3d objects [Cover of Winkler's book], [Demaines' at work; scroll to the bottom!] (Thanks to Erik Demaine for the links!)

(09/05): Labor Day Holiday.

(09/07): Entropy & Compression. (My notes. Scribe notes (tex, pdf).)
(09/12): Conditional Entropy, Divergence. Divergence Theorem. (My notes. Scribe notes (tex, pdf).)
(09/14): Mutual Information. Single-shot compression. (My notes. Scribe notes (tex, pdf).)
(09/19): Digression on Divergence. Universal Compression. Lempel-Ziv algorithm. (My notes. Scribe notes (tex, pdf).)
(09/21): Universal Compression. Markovian sources. Lempel-Ziv analysis. (See my notes for lecture 5. Also this paper. Scribe notes (tex, pdf).)
(09/26): Channel Coding. Binary Symmetric Channel. Coding theorem. Converse. (Notes from 2019. Scribe notes (tex, pdf).)
(09/28): Channel Coding (contd.): General Channels. Coding Theorem + Converse. Linear Coding and Compression. (Notes from 2019. Scribe notes (tex, pdf).)
(10/03): Polar coding. Linear compression. Overview of coding and analysis. (Notes from 2019. Scribe notes (tex, pdf).)
(10/05): Polar Coding: Decoding algorithm, Convergence goal. (Notes from 2019, Scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).)

(10/10): Columbus Day/Indigenous Peoples' Day

(10/12): Polar Coding: Martingales and Convergence. (Notes from 2019, Scribe notes (tex, pdf).)
(10/17): Communication Complexity. Basics. Inner Product, Discrepancy. Spectral bound.
(10/19): Communication Complexity of Set Disjointness.
(10/24): Compressing Interactive Communication.
(10/26): Information equals Amortized Communication.
(10/31): Information equals Amortized Communication (contd.).
(11/02): Streaming: Introduction, Algorithms and Lower Bounds.
(11/07): Data Structures. Model, Lower bound on prefix sum.
(11/09): Statistical Difference (SD). Role in Complexity. Toward SD reduces to its complement.
(11/14): SD reduces to its complement.
(11/16): Extensions complexity.
(11/21): Quantum information theory.

(11/23-11/27): Thanksgiving.

To be added