Computational Complexity
(2023, Jan–May)

Schedule: Monday, Wednesday at 09:30 — 11:00 (IST)

Problem sets and exams

  • Problem set 1: [PDF] (Due date: 2023-02-12)
  • Problem set 2: [PDF] (Due date: 2023-03-03)
  • Problem set 3: [PDF] (Due date: 2023-04-15)
  • Problem set 4: [PDF] (Due date: 2023-05-07)
  • Endsem (conceptual part): [PDF]
  • Endsem (take-home part): [PDF]

Lecture summary

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

Lecture 1 (Wednesday, 2023-01-18)
Administrivia, introduction to the course, rough course outline and problems of interest, definition of Turing machines
Lecture 2 (Monday, 2023-01-23)
Turing machines: alphabet reduction, tape reduction, universal Turing machines and simulations
Lecture 3 (Wednesday, 2023-01-25)
Non-determinism, definition of P and NP, two interpretations of NP, reductions, completeness
Lecture 4 (Monday, 2023-01-30)
NP-completeness, a not-so-interesting NP-complete language, CircuitSAT, the Cook-Levin theorem
Lecture 5 (Wednesday, 2023-02-01)
Web of reductions: CNF-SAT, 3SAT, Independent Set, 3-Colouring are all NP-complete
Lecture 6 (Monday, 2023-02-05)
wrapping completeness and reductions, co-sparse NP-complete languages imply P = NP, “collapses scale up; separations scale down”, self-reducibility and decision-to-search for NP
Lecture 7 (Wednesday, 2023-02-07)
The time-hierarchy theorems, proof of the deterministic time hierarchy theorem, Fortnow-Santhanam’s proof of the non-deterministic time hierarchy theorem.
Lecture 8 (Monday, 2023-02-12)
conclusion of time hierarchy theorems, oracle TMs, the Baker-Gill-Solovay theorem
Lecture 9 (Wednesday, 2023-02-14)
space complexity, space hierarchy theorems, relations between space and time, snapshot graphs, quantified boolean formulas
Lecture 10 (Monday, 2023-02-20)
PSPACE-completeness of TQBF, Savitch’s theorem, composition of logspace reductions
Lecture 11 (Wednesday, 2023-02-22)
NL-completeness of directed graph reachability, Immerman-Szelepcsenyi theorem
Lecture (Monday, 2023-02-27)
(problem set 1 solutions)
Lecture 12 (Wednesday, 2023-03-01)
Alternation and the polynomial hierarchy - definition via QBFs and also via oracles.
Lecture 13 (Monday, 2023-03-06)
Alternating TMs and connection to time and space classes, time-space tradeoffs for SAT.
Lecture 14 (Monday, 2023-03-13)
Time-space tradeoffs for SAT
Lecture 15 (Wednesday, 2023-03-15)
Circuits, non-uniformity and the Karp-Lipton-Sipser theorem
Lecture 16 (Wednesday, 2023-03-29)
Non-uniformity via TMs with advice, size hierarchy theorem, towards randomized complexity classes
Lecture 17 (Monday, 2023-04-03)
Randomised algorithms with one-sided error, two-sided error and zero-error, classes RP, coRP, BPP and ZPP
Lecture 18 (Wednesday, 2023-04-05)
Error reduction in randomised algorithm, BPP is in P/poly, towards showing BPP is in PH
Lecture 19 (Friday, 2023-04-07)
BPP is in Σ2 ∩ Π2 (Lautemann and Gacs-Sipser proofs), about the semantic definition of BPP and promise problems
Lecture 20 (Monday, 2023-04-10)
Introduction to interactive protocols, definitions of IP, interactive protocol for graph non-isomorphism, a brief crash-course on #P and permanent
Lecture 21 (Wednesday, 2023-04,12)
Interpolating polynomials, and interactive protocol for permanent
Lecture 22 (Monday, 2023-04-17)
Interactive protocol for #SAT and towards interactive protocols for TQBF
Lecture 23 (Monday, 2023-04-24)
Interactive protocol for TQBF, public coins vs private coin protocols, public coin protocol for graph-non-isomorphism
Lecture 24 (Wednesday, 2023-04-26)
Other properties of AM, revisiting graph isomorphism
Lecture 25 (Friday, 2023-04-28)
Lower bounds from algorithms - overview of Ryan Williams’ ACC lower bound
Lecture (Friday, 2023-05-12)
Going over problem set questions

Previous offerings of this course by the same instructor