[CSS.203.1]
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