CS60069 Computational Complexity
Instructor:
Swagato Sanyal.
Teaching Assistants:
Anamitra Mani, Anindya Ganguly.
Course overview:
This is a first course in computational complexity. Following is a tentative list of topics.
- Models of computation and the Turing Machine: Definitions and examples, motivation, universal Turing Machine, non-determinism.
- Time complexity classes: P, NP, coNP, EXP, NEXP, Reductions, Completeness, Cook-Levin Theorem.
- Space complexity: Classes PSPACE, L, NL, PSPACE and NL completeness.
- Diagonalization: Hierarchy Theorems, Ladner's Theorem, Oracle Turing Machines and limits of diagonalization.
- Polynomial Hierarchy.
- Boolean Circuits: P/Poly, BPP is in P/Poly, AC0, Lower bounds for AC0.
- Natural proofs.
- Randomized computation: Probabilistic Turing Machine, Classes RP, coRP, ZPP. Relationshp with circuit classes.
- Interactive proofs: Public coins and Arthur-Merlin games, class IP, IP=PSPACE.
- Concrete computational models: Decision trees, communication complexity.
- Complexity of counting: The class #P, #P-completeness, Toda's theorem.
Pre-requisites:
- A course on Formal Language and Automata Theory.
- A course on Design and Analysis of Algorithms.
- Mathematical maturity.
Classes:
Venue: CSE-107. Timings: Monday (12:00-12:55), Tuesday (10:00-10:55, 11:00-11:55), Thursday (08:00-08:55).
References:
- Computational Complexity A Modern Approach by Sanjeev Arora and Boaz Barak.