Special Topics Course: Computational Complexity Theory (2021)

Welcome #

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:

  1. Is verifying solutions harder than finding them?
  2. Does interacting with the prover help someone verifying the proof?
  3. Can we verify a proof by reading only a part of it?
  4. 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.

Contact #

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).

Lectures #

The meetings happen in P1 and P2.

  1. (Jan 13) Overview
  2. (Jan 18) Time and Space: Hierarchy
  3. (Jan 20) Constructibility and Time Hierarchy Theorem
  4. (Jan 25) Speedup Theorem
  5. (Jan 27) P and poly-time reductions
  6. (Feb 01) NP and coNP
  7. (Feb 03) Polynomial Hierarchy
  8. (Feb 08) PSPACE and QBF
  9. (Feb 10) REACH Algorithms and PSPACE
  10. (Feb 15) L and NL
  11. (Feb 17) NL = coNL

Evaluation #

Evaluation includes take-home assignments (10x4), a mid-sem quiz (20), a paper presentation (20), and end-sem viva (20).

References #

The lecture notes are here. A cleaned-up version of lecture notes

Now, a list of text books.

  1. Computational Complexity: A Modern Approach, Arora and Barak
  2. Computational Complexity: A Conceptual Perspective, Goldreich