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.

Course Description    Lectures    Problem sets    References   


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!

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:


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