Harvard University homepage
HARVARD.EDU

Madhu Sudan: Harvard CS 229r, Spring 2019: Information Theory in Computer Science

General Info

  • Lecturer: Madhu Sudan;  MD 339; email: first name at cs dot harvard dot edu; Office Hours: TuTh 1:15-2:15pm
  • TFs:
    • Mitali Bafna: MD 138; email first name dot last name at gmail dot com; Office hours and location: TuTh 4:30-5:30 @ LISE 319.
    • Noah Golowich: email ngolowich at college.
  • Lecture Time and Location: TuTh 12:00-1:15pm; 60 Oxford Street Room 330.

Other links for the course

Course announcement

Prereq: CS 121/124/125 or equivalents + Mathematical Maturity.
Time: TuTh 12:00pm – 1:15pm
Location: MD 221

Information Theory originated in the seminal work of Shannon (1948) that attempted to formalize and quantify communication. This theory was mostly ignored by theoretical computer science till the 1990s when tools and concepts from Information Theory started to play a central role in powerful results in the field. Notable examples include the Parallel Repetition Theorem of Raz (1994), the development of the Information Complexity measure as a means of understanding Communication Complexity (2001). Today Information Theoretic measures and tools influence many aspects of CS theory including analysis of streaming algorithms, differential privacy and game theory.  This course will introduce the basic concepts in information theory and then sample topics of interest to CS theory where information theoretic tools play a central role.

If you are interested (even tentatively) in the course, please sign up on the piazza site (piazza.com/harvard/spring2019/cs229r). Note that piazza will only allow self-registration by students with Harvard emails. If you do not have one (yet) please email Madhu.

Grading policy


Grades will be based on a combination of the following ingredients

  1. 3-5 Problem Sets. (40%)
  2. A course project (instructions to be posted shortly). (30%)
  3. Class Participation (biased towards the second half of the term). (15%)
  4. Additionally, you must scribe at least one lecture. Signup + Instructions Here (15%)
  • Piazza site: All announcements will be routed through this site – so please sign up right away!!
  • Canvas site: You will need this link to submit your problem sets

Announcements

  • Project Presentation Schedule is here. All presentations in LISE 303. (Room number corrected now – 4/30/2019!)
  • Practice Problem Set 4 (tex, pdf).
  • Problem Set 3 (tex, pdf).
  • Problem Set 2 (tex, pdf). Solutions (pdf).
  • Problem Set 1 (tex, pdf). Solutions (pdf).
  • Sign up for the course on Piazza. This will be principal forum for discussions and announcements. If you do not have a harvard email, send mail to Madhu to get enrolled.
  • Canvas will be the main mechanism for submitting psets and getting them graded. If you are not (yet) on canvas, submit your psets by email till you get added to canvas.
  • Sign up for scribing! Signup sheet here. Template for scribing (preamble, lect01.tex).

Topics (Tentative), Calendar and Handouts

  • Lecture 01 (Tue. 01/29): Introduction. Shearer’s Lemma. My notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 02 (Thu. 01/31): Entropy & Compression. Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 03 (Tue. 02/05): Conditional Entropy, Information, Divergence. Divergence Theorem. Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 04 (Thu. 02/07): Compression: Single-shot compression. Universal Compression. Markovian sources. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 05 (Tue. 02/12): Universal Compression. Lempel-Ziv. Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 06 (Thu. 02/14): Channel Coding. Notes. Preliminary (and final) scribe notes (tex, pdf).
  • Monday 02/18: Presidents’ Day Holiday
  • Lecture 07 (Tue. 02/19): Channel Coding (contd.): Converse theorem. Efficiency issues. Linear Coding and Compression. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes.
  • Lecture 08 (Thu. 02/21): Polar Codes. Overview. Principal Claims. Notes. Preliminary (and final) scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf).
  • Lecture 09 (Tue. 02/26): Polar Coding (contd.). Decoding. Analysis of (speed of) polarization. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes.
  • Lecture 10 (Thu. 02/28): Polar Coding wrapup. Communication Complexity – Basics. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 11 (Tue. 03/05): Communication Complexity. Inner Product, Discrepancy. Spectral bound. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 12 (Thu. 03/07): Communication Complexity of Set Disjointness. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 13 (Tue. 03/12): Communication Complexity of Set Disjointness. Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 14 (Thu. 03/14): Review of Future/Project topics. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf, v3.tex, v3.pdf). Final notes (v2, v3).
  • Sat. 3/16- Sun 3/24: Spring break
  • Lecture 15 (Tue. 03/26): Compressing Interactive Communication. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes.
  • Lecture 16 (Thu. 03/28): Information equals Amortized Communication. Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 17 (Tue. 04/02): Information equals Amortized Communication (contd.). Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 18 (Thu. 04/04): Parallel repetition – Introduction: Definition, Examples, Theorem, Key Lemma. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes. 
  • Lecture 19 (Tue. 04/09): Parallel repetition – Outline of construction and some considerations. Analysis omitted. Partial notes. Notes by Boaz Barak (includes most technical details). Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2). 
  • Lecture 20 (Thu. 04/11): Streaming: Introduction, Algorithms and Lower Bounds. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 21 (Tue. 04/16): Data Structures. Model, Lower bound on prefix sum. Notes. Preliminary scribe notes (tex, pdf). Final notes.
  • Lecture 22 (Thu. 04/18): Statistical Difference (SD). Role in Complexity. Toward SD reduces to its complement. Notes. Preliminary scribe notes (v1.tex, v1,pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 23 (Tue. 04/23): SD reduces to its complement. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 24 (Thu. 04/25): Extensions complexity. (No notes.) Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).
  • Lecture 25 (Tue. 04/30): Quantum information theory. Notes. Preliminary scribe notes (v1.tex, v1.pdf, v2.tex, v2.pdf). Final notes (v1, v2).

Reference Materials

  • The closest reference material may be notes from the last incarnation of this course – here.
  • The classic background text is Elements of Information Theory by Cover and Thomas. While it will not suffice for this course, it might come in handy.