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:
- Topics:
- Part 1: Compressing
Interactive Communication
- Part 2: Information =
Amortized Communication
- Part 3: Parallel Repetition
Theorem.
- Readings: Parts of
- Readings: Parts of L4-4.pdf, L4-5.pdf, L4-6.pdf, L5-2.pdf, L5-3.pdf