Special Topics Course: Computational Complexity Theory

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

• Is verifying solutions harder than finding them?
• Does interacting with the prover help someone verifying the proof?
• Can we verify a proof by reading only a part of it?
• Does randomness help in computation?

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 <bkomarath@iitgn.ac.in> or Bireswar Das <bireswar@iitgn.ac.in> for any course related queries. Prefix the subject line with "CS691:" (without double quotes).

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.

• Computational Complexity: A Modern Approach, Arora and Barak
• Computational Complexity: A Conceptual Perspective, Goldreich