Syllabus
If all goes well, we will be studying the following topics, in more-or-less the order given below.
- Discrete probability distributions, random variables (refresher)
- Definition of entropy
- Properties of entropy, Kullback-Leibler (KL) divergence
- Mutual information and its properties
- Entropy and data compression
- Error-correcting codes, communication through a noisy channel
- Sampling of applications of information theory in combinatorics
- Communication complexity and information complexity
- Applications to data structures
- Applications in optimization (extension complexity)
- Applications in game theory (parallel repetition)
- Further applications in combinatorics
Topics and Events, Day by Day
The table below will be updated throughout the term.
Any content that's colored light gray is tentative and subject to change.
| # | Date | Class Topics / Other Events | References |
|---|---|---|---|
| 1 |
Tue Jan 07 | Administrivia; review of probability, marginal and product distributions | |
| 2 |
Thu Jan 09 | Entropy, mutual information, KL-divergence; definitions and basic theorems | Lecture slides |
| 3 |
Fri Jan 10 | This x-hour was not used | |
| 4 |
Tue Jan 14 | Source coding; Kraft inequality; Shannon and Huffman codes | |
| 5 |
Thu Jan 16 | Shannon-Fano-Elias and arithmetic codes; Axiomatic entropy (interlude) | Lecture slides |
| 6 |
Fri Jan 17 | This x-hour was not used | |
| 7 |
Tue Jan 21 | Lempel-Ziv compression; Analysis under iid assumption | |
| 8 |
Thu Jan 23 | L-Z and Markov sources; Channel coding; rate, channel capacity, Shannon's theorem | |
| 9 |
Fri Jan 24 | [x-hour] Capacity of BSC and BEC; Key lemmas: DPI and Fano inequality | |
| 10 |
Tue Jan 28 | Proof of channel coding theorem: weak converse; achievability; probabilistic method | |
| 11 |
Thu Jan 30 | Adversarial channel; error correcting codes; Singleton bound; Reed-Solomon codes; Hamming and Shannon (Gilbert-Varshamov) bounds | |
| 12 |
Fri Jan 31 | This x-hour was not used | |
| 13 |
Tue Feb 04 | Chernoff-Hoeffding bounds; Combinatorial applications: Shearer's inequality; Loomis-Whitney inequality | |
| 14 |
Thu Feb 06 | More combinatorial applications: Set recovery problem; Bregman's theorem | |
| 15 |
Fri Feb 07 | This x-hour was not used | |
| 16 |
Tue Feb 11 | Introduction to communication complexity: EQUALITY problem, Rectangle property | |
| 17 |
Thu Feb 13 | Lower bounds for EQUALITY and INDEX problems; information cost for one-way protocols | |
| 18 |
Fri Feb 14 | This x-hour was not used | |
| 19 |
Tue Feb 18 | Information complexity formalized; direct sum theorems; DISJOINTNESS problem | Lecture notes |
| 20 |
Thu Feb 20 | Interactive information complexity; DISJOINTNESS lower bound | |
| 21 |
Fri Feb 21 | x-hour not used | |
| 22 |
Tue Feb 25 | Protocol compression: one-way and interactive; Direct sum results | |
| 23 |
Thu Feb 27 | Information = amortized communication (zoom talk to be posted later) | Rough notes |
| 24 |
Fri Feb 28 | x-hour not used | |
| 25 |
Tue Mar 04 | Final project presentations—I | See projects tab |
| 26 |
Thu Mar 06 | Final project presentations—II | See projects tab |