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:
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.