Welcome to CS691: Computational complexity theory. In this course, we will look at various computational models (TM, circuits) and the power enabled by various resources (time, space, size, depth). We will see that using this framework, we can formulate many natural real-world questions in concrete terms. Questions such as:
You are expected to be familiar with all topics covered in an undergraduate theory of computation course and algorithms course. In particular, a good understanding of Turing machines, analyzing time and space complexity of algorithms, reductions, and NP-completeness is assumed.
Please write to Balagopal Komarath <email@example.com> or Bireswar Das <firstname.lastname@example.org> for any course related queries. Prefix the subject line with "CS691:" (without double quotes).
The meetings happen in P1 and P2.
Evaluation includes take-home assignments (10x4), a mid-sem quiz (20), a paper presentation (20), and end-sem viva (20).
The lecture notes are here.
A cleaned-up version of lecture notes
Now, a list of text books.