[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)
- (tentative) Proof of the Cook-Levin theorem, some NP-completeness reductions, non-deterministic time hierarchy theorem
- Lecture 7 (2026-02-17)
- (tentative) Oracle machines and limits of diagonalisation (Baker-Gill-Solovay theorem)