- 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 :