COURSE DESCRIPTION
We will start this course by mathematically formalizing computation and algorithms. Our approach in the course would be to look at famous concrete problems and prove theorems about their uncomputability, or, if computable, then how fast can they be computationally solved. The problems we will cover in this course are: the halting problem, boolean formula satisfiability (the P!=NP question), quantified boolean formula, formula minimization, polynomial identity testing, undirected graph reachability, permanent and graph isomorphism. While studying these computational problems we will define various complexity classes and develop various tools used in modern complexity theory.Prerequisites: Theory of Computation.
Text Book: Arora & Barak, Computational Complexity (Cambridge University Press)
RECENT UPDATE
[03-Nov-17] Assignment 4 due on Tue, 14-Nov-17.
[12-Oct-17] Assignment 3 due on Fri, 27-Oct-17.
[08-Sep-17] MidSem Exam on Sat, 23-Sep-17, 1-3pm in KD102.
[08-Sep-17] Assignment 2 due on Wed, 20-Sep-17.
[10-Aug-17] Assignment 1 due on Thu, 24-Aug-17.
[28-Jul-17] Course begins on Mon, 31-Jul-17.