Computational Complexity Theory


Assumed background

Prerequisites include basic courses on algorithms, discrete maths, and theory of computing. In particular, please brush up a few topics like asymptotic notation, Turing machines, NP-completeness, and basic probability theory.

Course plan

We will follow the book by Sanjeev Arora and Boaz Barak, and will try to cover part 1 of it. I may add/delete some topics as we go on.

Reference books

  1. Computational Complexity: A Modern Approach by Sanjeev Arora, and Boaz Barak Online draft[AB]
  2. Computational Complexity by Christos Papadimitriou
  3. [CP]
  4. Introduction to the Theory of Computation by Michael Sipser
  5. [MS]
There are several online lecture notes. I will mention appropriate references from time to time.
Top

Evaluation

There will be two quizzes, midsem, and endsem. Top

Copying policy

While solving the assignments (and exams too!), you are not supposed to discuss with anyone (neither in your class nor anyone else). If at all you discuss an assignment problem with someone, name of that person should be mentioned while writing the solution of that particular problem. If you look up the solution on the Internet, the link to the solution should also be mentioned while writing it.

Any other form of copying implies a fail grade in the course. If you get stuck while solving the assignment, you are welcome to discuss with me.
Top

Assignments

Top

Lectures

Topics covered so far (refer to [AB] unless otherwise mentioned):

  1. Jan 28: Introduction: Computation, Universal Turing Machines, complexity classes (Parts of Chapters 0 and 1 of [AB])
  2. Feb 02: Equivalence of Turing machines, universal Turing machine, deterministic time hierarchy theorem (Chapter 1 and Section 3.1 of [AB], also see these notes)
  3. Feb 04: Reductions, P-completeness (see these notes) Also see this for the discussion on o(loglog n) space.
  4. Feb 09: Non-determinism, containment of NP in EXP and PSPACE, Proof of Cook-Levin theorem (Section 2.1 to 2.3 of [AB]), also see this
  5. Feb 11: co-NP, P,NP,EXP, NEXP, non-deterministic time hierarchy theorem. Here is the proof I presented in class.
  6. Feb 16: Ladner's theorem, Turing reductions, oracle Turing machines (Section 3.3, 3.4 of [AB])
  7. Feb 18: Oracle Turing machines, Turing reductions, Limits of diagonalization and Baker-Gill-Solovay theorem (Section 3.4 of [AB])
  8. Feb 23: Space complexity: Introduction, space constructibility, space hierarchy theorems, containments: L,NL in P, PATH is NL-complete, Savitch's theorem, PSPACE=NPSPACE (Chapter 4 of [AB])
  9. Feb 25: Immerman-Szelepsnyi theorem (Chapter 4 of [AB])
  10. Mar 2: TQBF and its PSPACE-completeness (Chapter 4 of [AB])
  11. Mar 4: Polynomial hierarchy (Chapter 5 of [AB])
  12. Mar 9: Circuit complexity: the classes P/poly, NC
  13. Mar 11: Karp-Lipton theorem, Meyer's theorem, Turing machines with advice (Chapter 6 of [AB] for both lectures)
  14. Mar 25: Randomized computation: BPP, RP, ZPP, BPP in P/poly
  15. Mar 30: Sipser-Gacs theorem (Chapter 7 of [AB]), introduction to IP (Section 8.1), interactive private coin protocol for graph non-isomorphism
  16. Apr 1: Definition of IP, IP is in PSPACE, #3SAT is in IP (Chapter 8 of [AB])
  17. Apr 06: Correctness of the interactive protocol for #3SAT, interactive protocol for QBF (Chapter 8 of [AB])