Lecturer: Madhu Sudan

**Lectures:
**

**Note: **Problem sets
corresponding to some of the lectures are available on
request. Please email Madhu if you wish to use those
in some course you are teaching.

- Day 1:

- Topics:
- Part 1: Shearer's
Lemma/Loomis-Whitney Inequality; Informal definition
of entropy + axioms; Implication: LWI/Shearer.

- Part 2: Formal definition of
entropy; proof of axioms; divergence theorem;
divergence; other stuff. Reading

- Part 3: Entropy vs/
Compression: single-shot; multi-shot; prefix-free
compression;

- Reading(s): Some subset of L1-1.pdf, L1-2.pdf, L1-3.pdf

- Day 2:
- Topics:
- Part 1: Kraft's inequality; Shannon
compression; Huffman compression. Markovian
Sources. Universal Compression.

- Parts 2 & 3: Lempel-Ziv. Claims. Parts of
Proofs.

- Reading(s): Some subset of L2-1.pdf, L2-2.pdf, L2-3.pdf and L2-4.pdf. (Addendum: See
also this
paper with David Xiang for a full analysis of LZ
compression.)

- Day 3:

- Topics:

- Part 1: Error-correction.
Binary symmetric channel. Capacity
and (speed of) convergence to capacity.

- Part 2: Polar codes.
Martingales and polarization theorem. Encoding,
Decoding.

- Part 3: Strong Polarization of
the polar-code-martingale.

- Reading(s): Parts of L2-3.pdf, L2-4.pdf, L3-1.pdf,
L3-2.pdf and L3-3.pdf.

- Day 4:
- Topics:
- Part 1: Introduction to
Communication Complexity.

- Parts 2 & 3: Information
Complexity and Lower bound on Disjointness.

- Reading(s): Parts of L4-0.pdf, L4-1.pdf, L4-2.pdf.

- Day 5: