General Info:
- Lecturer:
Madhu
Sudan; MD 339; email: first name at cs dot
harvard dot edu; Office Hours: TuTh 5-6pm (tentative)
- TF:
Preetum Nakkiran:
MD 334; email first name at cs dot harvard dot edu;
Office hours and location: TBD.
- Lecture Time and Location: TuTh
1:00-2:30pm; Room MD 221.
Other links for the course:
Announcements:
- Project presentations and writeup:
- Presentations on Thursday April 26th. Schedule here.
(note pizza at 1pm and coffee at 2pm.).
- Writeup due April 30th at 5pm. Submission
link.
- Project topics: Preliminary list of topics here.
- PS3 (tex, pdf).
- PS2 (tex, pdf).
- PS1 (tex, 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/23): Introduction. Review of
Complexity. Notes. Scribe
Notes (tex, pdf).
- Lecture 02 (Thu. 01/25): Diagonalization. Time/Space
Hierarchy. Relativization. Notes.
Scribe Notes (tex, pdf).
- Lecture 03 (Tue. 01/30): Circuits and Formulas. Circuit
size vs. Time Complexity. Branching Programs and Space.
Counting arguments. Neciporuk bound. Notes. Scribe notes (tex, pdf).
- Lecture 04 (Thu. 02/01): Non-determinism. Circuit Sat. P
vs. NP. Cook vs. Karp reductions. NP vs. CoNP. Notes. Scribe notes (tex, pdf).
- Lecture 05 (Tue. 02/06): Space Complexity. PSPACE, L,
NL, Savitch's theorem. NL=CoNL. Notes.
Scribe notes (tex, pdf).
- Lecture 06 (Thu. 02/08): Alternation. Time vs. Space vs.
Alternation. Fortnow's theorem. Notes.
Scribe notes (tex, pdf).
- Lecture 07 (Tue. 02/13): Alternation contd.: Debates,
Polynomial Hierarchy, Karp-Lipton Theorem. Notes.
- Lecture 08 (Thu. 02/15): Randomness. Promise problems.
Randomized complexity classes: ZPP, RP, CoRP, BPP. Notes. Scribe notes (tex, pdf).
- Monday 02/19: Presidents' Day
Holiday
- Lecture 09 (Tue. 02/20): BPP is contained in P/Poly
intersect PH. Notes. Scribe
notes (tex, pdf).
- Lecture 10 (Thu. 02/22): Complexity of Unique SAT.
Counting problems. #P. Permanent is #P-complete. Notes. Scribe notes (tex, pdf).
- Lecture 11 (Tue. 02/27): Approximate counting in
PH. Relativized separation of PH from #P. Parity vs. AC0.
Notes. Scribe notes (tex, pdf).
- Lecture 12 (Thu. 03/01): Parity is not in AC0. Begin
Toda's Theorem. Notes.
- Lecture 13 (Tue. 03/06): Complete proof of Toda's
Theorem. Notes.
- Lecture 14 (Thu. 03/08): Average case complexity. Notes.
- Sat. 3/10- Sun 3/18: Spring break
- Lecture 15 (Tue. 03/20): Interaction. IP, AM, MA. Notes.
- Lecture 16 (Thu. 03/22): IP = PSPACE. Notes.
- Lecture 17 (Tue. 03/27): Probabilistically checkable
proofs. Inapproximability. (No notes.)
- Lecture 18 (Thu. 03/29): NP in PCP(poly(n),O(1)). Notes.
- Lecture 19 (Tue. 04/03): Dinur's proof of the PCP
theorem - Part I. Notes.
- Lecture 20 (Thu. 04/05): Dinur's
proof of the PCP theorem - Part II. (no notes).
- Lecture 21 (Tue. 04/10): Guest lecture by Preetum: Zero
Knowledge.
- Lecture 22 (Thu. 04/12): Guest lecture by Preetum:
Quantum Computing.
- Lecture 23 (Tue. 04/17): ETH,
SETH, and Fine-grained Complexity - I. Notes.
- Lecture 24 (Thu. 04/19): ETH, SETH, and Fine-grained
Complexity - II.
- Lecture 25 (Tue. 04/24): Total functions, PHP, PPAD and
NASH.
Reference Materials: