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 |
Thu Jan 05 | Administrivia; review of probability, marginal and product distributions | |
| X |
Fri Jan 06 | x-hour not used | |
| 2 |
Tue Jan 10 | Entropy, mutual information, KL-divergence; definitions and basic theorems | Lecture slides |
| 3 |
Thu Jan 12 | Source coding; Kraft inequality; Shannon and Huffman codes | |
| X |
Fri Jan 13 | x-hour not used | |
| 4 |
Tue Jan 17 | Shannon-Fano-Elias and arithmetic codes; Axiomatic entropy (interlude) | Lecture slides |
| 5 |
Thu Jan 19 | Lempel-Ziv compression; Analysis; Markov sources | |
| X |
Fri Jan 20 | x-hour not used | |
| 6 |
Tue Jan 24 | Channel coding; rate and channel capacity; converse theorem; DPI and Fano inequality | |
| 7 |
Thu Jan 26 | Channel coding: achievability; probabilistic method | |
| X |
Fri Jan 27 | x-hour not used | |
| 8 |
Tue Jan 31 | Adversarial channel; error correcting codes; Singleton bound; Reed-Solomon codes | |
| 9 |
Thu Feb 02 | Volume bound; Gilbert-Varshamov bound; Hamming codes; Chernoff-Hoeffding bounds | |
| X |
Fri Feb 03 | x-hour not used | |
| 10 |
Tue Feb 07 | Combinatorial applications: Loomis-Whitney inequality; Shearer inequality; Bregman's theorem | |
| 11 |
Thu Feb 09 | More combinatorial applications: set recovery; union-closed conjecture | Boppana's paper |
| X |
Fri Feb 10 | x-hour not used | |
| 12 |
Tue Feb 14 | Introduction to communication complexity: EQUALITY problem | |
| 13 |
Thu Feb 16 | Information complexity: INDEX problem, direct sum | |
| X |
Fri Feb 17 | x-hour? tbd | |
| 14 |
Tue Feb 21 | More direct sum: EQUALITY, DISJOINTNESS; interactive information complexity | Lecture notes |
| 15 |
Thu Feb 23 | Information complexity of AND; progress towards general direct-sum | |
| X |
Fri Feb 24 | x-hour? tbd | |
| 16 |
Tue Feb 28 | Information equals amortized communication | |
| 17 |
Thu Mar 02 | Final project presentations—I | |
| X |
Fri Mar 03 | x-hour unlikely to be used | |
| 18 |
Tue Mar 07 | Final project presentations—II |