[CSS.203.1]
Computational Complexity
(2026, Jan–May)
Schedule: Tuesdays and Thursdays at 14:00 — 15:30 (IST)
Problem sets and exams
- Problem set 1: [PDF] (Due date: 2026-02-23)
Lecture summary
Summary scribes:
[PDF] [git repo (only internally accessible)]
Handwritten notes: [Dropbox folder]
- Lecture 1 (2026-01-27)
- Introduction to the course, computing Boolean functions via Boolean circuits, universality of circuits, and existence of “hard” functions
- Lecture 2 (2026-01-29)
- Size hierarchy theorem, building a circuit for circuit evaluation, circuit families computing uncomputable functions
- Lecture 3 (2026-02-03)
- (tentative) Introduction to Turing machines, tape reduction and alphabet reduction, universal TMs
- Lecture 4 (2026-02-05)
- Classes P, E and EXP, deterministic time hierarchy theorem, introduction to non-determinism
- Lecture 5 (2026-02-10)
- Reductions between languages (many-one, Turing etc.), definition of NP completeness
- Lecture 6 (2026-02-13)
- Proof of the Cook-Levin theorem, some NP-completeness reductions
- Lecture 7 (2026-02-17)
- Padding arguments, non-deterministic time hierarchy theorem, introduction to oracle machines
- Lecture 8 (2026-02-19)
- Limits of diagonalisation – Baker-Gill-Solovay theorem, Fortune and Mahaney’s theorem
- Lecture 9 (2026-02-24)
- Polynomial hierarchy, complete problems for Σi and Πi, why PH is unlikely to have complete problems
- Lecture 10 (2026-02-26)
- Self-reducibility of SAT, Karp-Lipton theorem, TMs with advice and reconnecting with circuits
- Lecture 11 (2026-03-05)
- Introduction to space complexity, TQBF is in PSPACE, graph-connectivity is in NL
- Lecture 12 (2026-03-10)
- Savitch’s theorem, PSPACE completeness of TQBF and GeneralisedGeography
- Lecture 13 (2026-03-12)
- (tentative) Why many space-complexity proofs do not relativise, introduction to logspace-reductions, NL-completeness of graph-connectivity
- Lecture 14 (2026-03-17)
- (tentative) Read-once certificate description of NL, proof of the Immerman-Szelepcsényi theorem
- Lecture 15 (2026-03-19)
- (tentative)
- Lecture 16 (2026-03-24)
- (tentative)
- Lecture 17 (2026-03-26)
- (tentative)
- Lecture 18 (2026-03-31)
- (tentative)
- Lecture 19 (2026-04-02)
- (tentative)
- Lecture 20 (2026-04-07)
- (tentative)
- Lecture 21 (2026-04-09)
- (tentative)