Program Overview

Course Information

The course Computational Complexity was offered in 2025, from January to May.

Schedule

The course was scheduled to take place on Wednesdays and Fridays at 14:00 — 15:30 (IST).

Problem Sets and Exams

The course included the following problem sets:

• Problem set 0:
• Problem set 1:
• Problem set 2:
• Problem set 3:

Lecture Summary

The course covered the following topics:

1. Administrivia, introduction to the course, rough course outline and problems of interest, definition of Turing machines
2. Turing machines, tape reduction, alphabet reduction, notion of time complexity, Universal TM and simulation
3. Introduction to non-determinism via regular expressions, non-deterministic finite automatas, definition of NTIME, and NP
4. Notion of reductions (many-one reductions, Turing reductions, projections), examples of reductions between problems in NP and coNP
5. NP-completeness, Proof of the Cook-Levin theorem, NP-completeness of clique
6. Introduction to diagonalisation and proof of the deterministic time hierarchy theorem, thoughts about extending to the non-deterministic machines
7. Completing the proof of the non-deterministic time hierarchy theorem, introduction to oracle TMs and the Baker-Gill-Solovay theorem
8. Completing the proof of Baker-Gill-Solovay, introduction to PNP and NPNP, the lsb-of-lex-largest-sat-assignment problem, Σ2-SAT
9. Σ2-SAT is NPNP-complete, definition of the polynomial hierarchy, PH collapses if Σi equals Πi
10. Padding arguments, versions of Mahoney's theorem (unary / co-sparse NP-hard languages imply P = NP), introduction to space complexity
11. Definition of DSPACE(s(n)) and NSPACE(s(n)), introduction to L, NL, PSPACE, NPSPACE etc., TQBF is in PSPACE
12. TQBF is PSPACE-complete, Savitch's theorem, PSPACE = NPSPACE, Generalised-Geography is PSPACE-complete
13. Introduction to logspace reductions, NL-completeness, directed-path is NL-complete, high-level overview of Reingold's result (undirected-path is in L)
14. Read-once certificates for NL, and the Immerman-Szelepcsényi theorem
15. Introduction to catalytic space
16. Tree-Evaluation problem, the Cook-Mertz theorem
17. Ryan Williams' breakthrough – simulating time with ~square-root space
18. Introduction to circuits, size hierarchy theorem, Karp-Lipton-Sipser theorem
19. Low-depth circuits, Addition in AC0, Razborov-Smolensky's theorem (Parity is not in AC0)
20. Finishing the proof of Razborov-Smolensky theorem, Majority is not in AC0, introduction to randomised classes RP, coRP and BPP, error reduction
21. Introduction to ZPP, an example of a problem in ZPP, showing that ZPP = RP ∩ coRP, proving BPP is in P/poly
22. Gacs-Sipser-Lautemann theorem: BPP is in Σ2 ∩ Π2, brief introduction to AM and MA, sketch of why GI is unlikely to be NP-hard
23. Relation between AM, coAM, proving that graph-non-isomorphism is in AM via the Goldwasser-Sipser set-size protocol
24. Hardness vs randomness: introduction to pseudorandom generators and why we believe BPP = P
25. Combinatorial designs and the Nisan-Wigderson theorem

Previous Offerings

This course was previously offered in:

• 2024 at TIFR
• 2023 at TIFR
• 2021 at TIFR