COMSE6998: Information Theory in Theoretical Computer Science

Welcome to COMSE6998 Information Theory in Theoretical Computer Science!

Time: Wednesday 10:10 - 12:30.

Location: The vast majority of the course will be delivered online (via Zoom). Depending on COVID19 health conditions, we may hold a small number of in-person classes ealy in the semester.

Instructor: Omri Weinstein (Room: TBD. Office Hours: Wednesday 12:30-13:30).

TA: Hengjie Zhang (Room : TBD. Office Hours: Friday 13:00-14:00)

Course Description

Information theory plays a key role in error-correcting codes, compression, ML and digital communication, but it is also a powerful mathematical tool for analyzing computation in various models, and found many applications in combinatorics, graph theory and theoretical computer science.

The primary goal of this course is to develop tools in information theory and communication complexity, and use them to prove upper and lower bounds on important problems in theoretical CS, such as linear programs, interactive compression, streaming algorithms, data structures and locally-decodable codes.

This is an advanced course geared towards CS and EE graduate students, though it is designed to be self-contained. Evaluation is based on homeworks and a final project (reading, implementation, or research). The class satisfies the track electives for Theory (Foundations) track. Prerequisites

Prerequisites

There are no mandatory prerequisites other than familiarity with probability theory and linear algebra. Background in Complexity Theory (e.g., COMS 4236) and information theory is recommended but not a prerequisite. However, mathematical maturity is a must, and lectures are based on theoretical ideas and will be proof-heavy. Students are expected to be able to read and write formal mathematical proofs.

Textbooks

  1. Elements of Information Theory, by Thomas M. Cover and Joy A. Thomas [Download] .
  2. Communication Complexity, by Anup Rao and Amir Yehudayoff [Download] .

Assignments

Not available yet.

Lecture notes

Lecture notes will be posted every week.
  1. Lecture 1.
  2. Lecture 2.

Tentative Syllabus

For more information of the syllabus, see Syllabus.pdf .

Grading

There will be a bi-weekly HW assignment (~5 in total). Grading will be based on

In the final project, you are expected to explore and extend a research paper related to the course's topic (There will be a list of papers to choose from, but you are free to suggest a project subject to approval by the instructor and the TA).

Relavent Courses

References