COURSE DESCRIPTION
We will start this course by mathematically formalizing computation and algorithms. Our approach in the course would be then to look at various 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
[31-Mar-14] Assignment 3 is due by 12-Apr-14.
[09-Mar-14] Extra talks scheduled.
[06-Feb-14] Assignment 2 is due by 26-Feb-14.
[12-Jan-14] Assignment 1 is due by 29-Jan-14.
[29-Dec-13] Course begins on Tue, 31-Dec-13.