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 :
  • Assignment 1 (due date: August 31, 2013)
  • Assignment 2 (due date: September 30, 2013)
  • Assignment 3 (due date: October 30, 2013)
  • Assignment 4 (due date: November 20, 2013)