## Computational Complexity Theory

• Instructor : Chandan Saha   Course number and Credits : E0 224 and 3:1   Lecture time : M,W 11:30-13:00   Venue : CSA 117

• Objective : Computational complexity theory is the fundamental subject of classifying computational problems based on their `complexities'. In this context, `complexity' of a problem is a measure of the amount of resource (time/space/random bits, or queries) used by the best possible algorithm that solves the problem. The aim of this course is to give a basic introduction to this field. Starting with the basic definitions and properties, we intend to cover some of the classical results and proof techniques of complexity theory.

• Syllabus : Introduction to basic complexity classes - P, NP, coNP, PSPACE, EXP, L, NL etc.; Notion of `reductions' and `completeness'; Diagonalization - Time hierarchy theorem & Ladner's theorem; Space bounded computation; Polynomial time hierarchy (PH); Boolean circuit complexity; Randomized computation; Interactive proofs (IP); Brief introduction to PCP theorem and hardness of approximation; Complexity of counting - class #P.

• References : A. The book titled `Computational Complexity - A Modern Approach' by Sanjeev Arora and Boaz Barak. B. Lecture notes of similar courses as and when required.

• Prerequisites : Basic familiarity with undergraduate level theory of computation and data structures & algorithms would be helpful. More importantly, some mathematical maturity with an inclination towards theoretical computer science.

• Grading policy : Assignments - 40%; Mid-term exam - 30%; End-term exam - 30%

• Lecture notes : This course will closely follow part one of the book, Computational Complexity - A Modern Approach by Sanjeev Arora and Boaz Barak. An online copy of a draft of this book is available here

• Assignments :