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

• Lecture 1: Introduction and motivation for this course.
• Lecture 2: Entropy and source coding.
• Lecture 3: Conditional entropy and Shearer’s Lemma.
• Lecture 4: Divergence, mutual information and basic inequalities.
• Lecture 5: Deterministic Communication Complexity.
• Lecture 6: Randomized Communication Complexity.
• Lecture 7: Interactive Compression and Direct Sums.
• Lecture 8: Information Cost, Hellinger Distance and a Randomized LB for Disjointness.
• Lecture 9: Applications: Streaming Lower Bounds.
• Lecture 10: Intro to the Cell Probe model and Predecessor Search.
• Lecture 11: The Cell-Sampling Method, Dictionaries and Succinct Data Structures.
• Lecture 12: Lopsided Set Disjointness and the Cell-Sampling Method.
• Lecture 13: Dynamic data structure lower bounds.
• Lecture 14: Epilogue.

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

• homework (35%)
• scribing 1 lecture (15%)
• final project (50%)

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

• Information and Coding Theory, by Madhur Tulsiani. [link]
• Information Theory and its applications in theory of computation, by Venkatesan Guruswami, Mahdi Cheraghchi. [link]
• Communication Complexity, by Shachar Lovett. [link]
• Course, Communication Complexity, by Prahladh Harsha, Jaikumar Radhakrishnan, Meena Mahajan. [link]

References

• Book, Communcation Complexity, by Anup Rao, Amir Yehudayoff . [link]
• Book, Communication Complexity (for Algorithm Designers), by Tim Roughgarden. [link]
• Book, Communication Complexity, by Eyal Kushilevitz, Noam Nisan. [link]
• Paper, Entropy and Counting, by Jaikumar Radhakrishnan. [link]