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)
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
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.
For more information of the syllabus, see Syllabus.pdf .
There will be a bi-weekly HW assignment (~5 in total). Grading will be based on