Computational Complexity
(2024, Jan–May)

Schedule: Tuesday, Thursday at 09:30 — 11:00 (IST)

Problem sets and exams

  • Problem set 0: [PDF] (optional; recommended for those without prior background in automata theory)
  • Problem set 1: [PDF] (Due date: 18 Feb 2024, last addition on 6 Feb 2024)
  • Problem set 2: [PDF] (Due date: 9 Mar 2024, last addition on 22 Feb 2024)
  • Problem set 3: [PDF] (Due date: 15 Apr 2024, last addition on 30 Mar 2024)

Lecture summary

Summary scribes: (only accessible internally)
[PDFs] [ZIP] [git repo]

Lecture 1 (2024-01-16)
Administrivia, introduction to the course, rough course outline and problems of interest, definition of Turing machines
Lecture 2 (2024-01-18)
Formal description of TMs and languages accepted by them, tape reduction, alphabet reduction, definition of universal Turing Machines, the class P.
Lecture 3 (2024-01-23)
Motivating non-determinism via automatas (aside: cloudflare outage), definition of non-determinism in TMs, the class NP and coNP, introducing CircuitEval, CircuitSAT, Tautology
Lecture 4 (2024-01-25)
Notion of reductions, Turing reductions and many-one-reductions, statement of the Cook-Levin theorem, reductions between independent set, clique, vertex cover, CNF-SAT, CircuitSAT etc.
Lecture 5 (2024-01-30)
Reductions to 3-colouring, introduction to computational tableau, proof of the Cook-Levin theorem
Lecture 6 (2024-02-06)
Padding arguments, proof of the deterministic time hierarchy theorem
Lecture 7 (2024-02-08)
Time-constructible functions, non-deterministic time hierarchy theorem
Lecture 8 (2024-02-13)
Ladner’s theorem - existence of NP-intermediate languages (assuming P != NP)
Lecture 9 (2024-02-15)
Oracle Turing Machines, Baker-Gill-Solovay theorem
Lecture 10 (2024-02-22)
Self-reducibility of NP, Mahoney’s theorem, introduction to the polynomial hierarchy
Lecture 11 (2024-02-27)
Polynomial hierarchy, complete problems, equivalence of Σ2 with NPNP etc.
Lecture 12 (2024-02-29)
Introduction to space complexity, classes such as L, NL, PSPACE, NPSPACE, configuration graphs and reachability, TQBF is PSPACE-complete and PSPACE = NPSPACE
Lecture 13 (2024-03-05)
(Instructor: Prahladh Harsha) Introduction to logspace machines, Savitch’s theorem, logspace reductions and properties
Lecture 14 (2024-03-07)
(Instructor: Prahladh Harsha) Non-deterministic logspace, NL-completeness, the PATH problem is NL-complete, read-once certificates for NL, Immerman-Szelepcsényi theorem
Lecture 15 (2024-03-12)
Wrapping up Immerman-Szelepcsényi theorem, introduction to circuits and non-uniformity, definition of AC0, NC0, AC1, NC1 etc., addition in AC0
Lecture 16 (2024-03-14)
Razborov-Smolensky’s proof that Parity is not in AC0
Lecture 17 (2024-03-19)
Circuit size hierarchy theorem, Karp-Lipton theorem, non-uniformity and advice
Lecture 18 (2024-03-21)
Introduction to randomised complexity classes, success-probability amplification
Lecture 19 (2024-03-26)
Adleman/Bennett-Gill theorem and the Sipser-Gács-Lautemann theorem
Lecture 20 (2024-03-28)
ZPP and relation to RP and coRP, completeness for BPP, semantic vs syntactic classes, promise problems

No classes until Apr 20

Previous offerings of this course by the same instructor