[CSS.203.1]
Computational Complexity
(2025, Jan–May)
Schedule: Wednesday, Friday at 14:00 — 15:30 (IST)
Problem sets and exams
- Problem set 0: [PDF] (Due date: 2025-02-07)
- Problem set 1: [PDF] (Due date: 2025-02-23)
- Problem set 2: [PDF] (Due date: 2025-03-25)
- Problem set 3: [PDF] (Due date: 2025-04-25)
Lecture summary
Summary scribes: (only accessible internally)
[PDF] [ZIP] [git repo]
- Lecture 1 (2025-01-24)
- Administrivia, introduction to the course, rough course outline and problems of interest, definition of Turing machines
- Lecture 2 (2025-01-27)
- Turing machines, tape reduction, alphabet reduction, notion of time complexity, Universal TM and simulation
- Lecture 3 (2025-01-30)
- Introduction to non-determinism via regular expressions, non-deterministic finite automatas, definition of NTIME, and NP.
- Lecture 4 (2025-02-05)
- Notion of reductions (many-one reductions, Turing reductions, projections). Examples of reductions between problems in NP and coNP.
- Lecture 5 (2025-02-07)
- NP-completeness, Proof of the Cook-Levin theorem, NP-completeness of clique
- Lecture 6 (2025-02-12)
- Introduction to diagonalisation and proof of the deterministic time hierarchy theorem. Thoughts about extending to the non-determistic machines.
- Lecture 7 (2025-02-14)
- Completing the proof of the non-deterministic time hierarchy theorem, introduction to oracle TMs and the Baker-Gill-Solovay theorem
- Lecture 8 (2025-02-19)
- Completing the proof of Baker-Gill-Solovay, introduction to PNP and NPNP, the lsb-of-lex-largest-sat-assignment problem, Σ2-SAT
- Lecture 9 (2025-02-21)
- Σ2-SAT is NPNP-complete, definition of the polynomial hierarchy, PH collapses if Σi equals Πi
- Lecture 10 (2025-02-24)
- Padding arguments, versions of Mahoney’s theorem (unary / co-sparse NP-hard languages imply P = NP), introduction to space complexity
- Lecture 11 (2025-02-26)
- (tentative) Definition of DSPACE(s(n)) and NSPACE(s(n)), introduction to L, NL, PSPACE, NPSPACE etc. TQBF is in PSPACE
- Lecture 12 (2025-03-05)
- TQBF is PSPACE-complete, Savitch’s theorem, PSPACE = NPSPACE, Generalised-Geography is PSPACE-complete
- Lecture 13 (2025-03-07)
- Introduction to logspace reductions, NL-completeness, directed-path is NL-complete, high-level overview of Reingold’s result (undirected-path is in L)
- Lecture 14 (2025-03-12)
- Read-once certificates for NL, and the Immerman-Szelepcsényi theorem
No class on 2025-03-14 and 2025-03-19
- Lecture 15 (2025-03-21)
- Introduction to catalytic space [handwritten notes] [Video]
- Lecture 16 (2025-03-26)
- Tree-Evaluation problem, the Cook-Mertz theorem [handwritten notes] [Video]
- Lecture 17 (2025-03-28)
- Ryan Williams’ breakthrough – simulating time with ~square-root space [handwritten notes] [Video]
- Lecture 18 (2025-04-02)
- Introduction to circuits, size hierarchy theorem, Karp-Lipton-Sipser theorem
- Lecture 19 (2025-04-04)
- Low-depth circuits, Addition in AC0, Razborov-Smolensky’s theorem (Parity is not in AC0)
- Lecture 20 (2025-04-09)
- Finishing the proof of Razborov-Smolensky theorem, Majority is not in AC0, introduction to randomised classes RP, coRP and BPP, error reduction
- Lecture 21 (2025-04-11)
- Introduction to ZPP, an example of a problem in ZPP, showing that ZPP = RP ∩ coRP, proving BPP is in P/poly
- Lecture 22 (2025-04-16)
- Gacs-Sipser-Lautemann theorem: BPP is in Σ2 ∩ Πi, brief introduction to AM and MA, sketch of why GI is unlikely to be NP-hard
- Lecture 23 (2025-04-18)
- Relation between AM, coAM, proving that graph-non-isomorphism is in AM via the Goldwasser-Siper set-size protocol
- Lecture 24 (2025-04-23)
- Hardness vs randomness: introduction to pseudorandom generators and why we believe BPP = P
- Lecture 25 (2025-04-25)
- (tentative) Combinatorial designs and the Nisan-Wigderson theorem