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).
(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/09): Statistical Difference (SD). Role in Complexity. Toward SD reduces to its complement.
(11/16): Extensions complexity.
(11/21): Quantum information theory.
(11/23-11/27): Thanksgiving.
(11/28): TBD
(11/30): TBD
To be added
Grading and Policy (TBD)
Resources: (Ed, Gradescope, Calendar, ...)