15-859: Information Theory and its applications in theory of
computation, Spring 2013
- Instructors: Venkatesan Guruswami
and Mahdi Cheraghchi
- Time: Tuesdays & Thursdays, 12:00-1:20 PM, GHC
4303.
- Office hours: By appointment.
Lectures
The course notes posted here are scribed by students and are not at all
proof-read or checked for accuracy and correctness. The lecture sketches are more like a quick snapshot of the board work, and will miss details and other contextual information mentioned but not written during lecture. Please use the materials at your own risk!
- Lecture 1 (VG): Introduction, Entropy, Kraft's inequality
- Lecture 2 (VG): Source coding theorem, conditional entropy,
mutual information.
- Lecture 3 (VG): KL-divergence and connections
- Lecture 4 (VG): KL-divergence and Chernoff bounds, Data
processing and Fano's inequalities, Asymptotic Equipartition
Property (AEP).
- Lecture 5 (MC): Universal source coding: Lempel-Ziv algorithm
and proof of its optimality.
- Lecture 6 (MC): Source coding via typical sets and
universality, joint typicality and joint AEP, discrete channels
and channel capacity.
- Lecture 7 (MC): Proof of Noisy channel coding theorem.
- Lecture 8 (VG): Converse to coding theorem, Joint source-channel coding theorem, BSC and BEC revisited, Linear codes.
- Lecture 9 (VG): Constructing capacity-achieving codes via concatenation; Introduction to Polarization.
- Lecture 10 (VG): Arikan's recursive construction of a polarizing invertible transformation
- Lecture 11 (VG): Polar codes construction
- Lecture 12 (VG): Wrap-up polar codes; Moser's entropy compression argument for bounded occurrence k-SAT
- Lecture 13 (MC): Bregman's theorem; Shearer's Lemma and applications.
- Lecture 14 (MC): Source coding and Graph entropy
- Lecture 15 (MC): Applications of Graph entropy
- Lecture 16 (MC): Monotone formula lower bounds via graph entropy
- Lecture 17 (VG): Introduction to (deterministic) communication complexiy
- Lecture 18 (VG): Rectangle size and rank methods; Introduction to randomized communication complexiy
- Lecture 19 (VG): Randomized vs. deterministic; Public coin vs. private coins; Randomized vs. distributional communication complexiy
- Lecture 20 (VG): Discrepancy method; Application to Dot Product; Indexing lower bound via information theory
- Lecture 21 (VG): Set Disjointness lower bound via product distribution
- Lecture 22 (MC): Optimal set Disjointness lower bound and applications; Information Cost measure
- Lecture 23 (MC): Compression of constant round protocols to information cost
- Lecture 24 (MC): Compression of arbitrary communication protocols
- Lecture 25 (VG): Parallel repetition of 2-prover 1-round games
- Lecture 26 (VG): Parallel repetition theorem -- some proof ingredients
Problem sets
Course Description
Information theory was introduced by Shannon in the late 1940s as a
mathematical theory to understand and quantify the limits of
compressing and reliably storing/communicating data. Since its
inception, in addition to its pivotal role in digital
communications, the subject has broadened to find applications in
many different areas of science and engineering. In recent years,
information-theoretic techniques and intuition have also been
playing an increasingly prominent role in theoretical computer
science. This course will cover the basic notions in information
theory, followed by a sample of diverse applications in theoretical
computer science and related mathematics that use techniques from
information theory. The following is a suggestive list of possible
topics:
- Basic notions: entropy, mutual information, KL divergence,
and their properties.
- Applications in combinatorics and graph theory
- Channel and source coding.
- Capacity achieving codes: concatenated codes and polar codes.
- Information theory methods in communication complexity
- Further applications: Data structures, locally decodable
codes, metric embeddings, parallel repetition, etc.
- Kolmogorov Complexity and Lovasz Local Lemma.
References
Recommended reference book on basics of information theory is
``Elements of Information Theory'' by T. M. Cover and J. A. Thomas
(Second Edition, Wiley). The rest of the material will be based on
the lecturers' experience and related research papers or surveys.
Materials from the following related courses might be useful in
various parts of the course:
You can also check out Aarti Singh's spring 2012 CMU course
Information Processing and Learning that explores the theme of
information theory as a common ground between signal processing and
machine learning.
Intended audience: Graduate students in computer science,
mathematics, electrical engineering with theoretical interests.
Interested undergraduate students with very strong mathematical
skills.
Prerequisites: Mathematical maturity and a working
knowledge of probability theory.
Grading: Based on problem sets, scribe notes, and,
depending on class size, possible student presentations/projects.
There will be no exams.
Maintained by Venkatesan Guruswami