Classes per week
3 Lectures + 1 Tutorial
- Module 1: Introduction, P and NP - Review of Turing machines, universal Turing machines, and uncomputable functions, P vs. NP, NP vs. co-NP, and NP-completeness, EXP, NEXP
- Module 2: Cook Levin's Theorem
- Module 3: Diagonalization, Space complexity (Savitch's Theorem, Immerman-Szelepchenyi Theorem, and Reyngold's Theorem.), Polynomial Hierarchy
- Module 4: Interactive Proofs - PCP theorem and its application to approximability, Queery Complexity, Communication Complexity
- Module 5: Circuit complexity and lower bounds
- Module 6: Hardness vs. Randomness - Randomized Computation, derandomization, Pseudo-random generators
- Module 7: Polynomial identity testing vs Lower bounds for arithmetic circuits
- S. Arora and B. Barak, ``Computational Complexity: A Modern Approach'', Cambridge University Press.
- O. Goldreich, ``Computational Complexity: A conceptual perspective'', Cambridge University Press.
- C. H. Papadimitriou, Computational Complexity, Pearson Education.
- J. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Education.