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
  2. Computational Complexity by Christos Papadimitriou
  3. Introduction to the Theory of Computation by Michael Sipser
There are several online lecture notes. I will mention appropriate references from time to time.
Top

Evaluation

There will be two assignments, midsem, and endsem. In addition to this, there will be a project where you will be assigned paper(s) to read. You will have to give a 30 minutes presentation on your project. The weightage is as follows:
  1. Assignments: 20
  2. Midsem: 20
  3. Endsem: 40
  4. Project: 20
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.

There are problem sets which you need not submit and are free to discuss with each other.

Assignments and Problem sets

Note: Please read the Copying policy before you start solving the assignment. The solutions/hints will be posted on the deadline. Hence no late submissions are allowed.
Top

Lectures

Topics covered so far:

  1. 4th Jan: Introduction to computational complexity, Turing machines, Universal Turing machine, introduction to some complexity classes like P,NP,EXP,NEXP,PSPACE,L,NL and their relationship.

  2. 8,11 Jan: no class

  3. 15th Jan: NP-completeness, Cook-Levin theorem
  4. 18th Jan: Parsimonious reductions, Levin reductions, Decision vs search, Deterministic time hierarchy theorem
  5. 22nd Jan: Non-deterministic time hierarchy theorem (see this and this for some details of the proof)
  6. 25th Jan: Baker-Gill-Solovay theorem
  7. 29th Jan: Space-bounded computation: Introduction and examples of logspace algorithms, NL algorithm for directed reachability, Savitch's theorem
  8. 1st Feb: Directed reachability is NL-complete, Immerman-Szelepcsenyi theorem (Ref: Section 4 of this
  9. 5th Feb: Immerman-Szelepcsenyi theorem continued
  10. 8th Feb: Polynomial time hierarchy
  11. 12th Feb: Polynomial time hierarchy, RL algorithm for undirected reachability
  12. 15th Feb: Probabilistic TMs, BPP and RP, containments of complexity classes
  13. 19th Feb: Error reduction in BPP, Sipser-Gacs theorem
  14. 22nd Feb: Problem solving session, midsem
  15. 5th March: Circuit complexity: P/poly, uniformity, Karp-Lipton theorem
  16. 8th March: Meyer's theorem, existence of hard functions, NC and AC classes, non-uniform hierarchy theorem
  17. 12th March: BPP and P/poly, Interactive proofs: introduction, interactive protocol for GNI
  18. 15th March: AM, public coins interactive protocol for GNI
  19. 19th March: IP=PSPACE
  20. 22nd March: IP=PSPACE continued, introduction to counting: the class \#P
  21. 26th March: PP, \#P-completeness, Valiant-Vazirani theorem
  22. 2nd April: Toda's theorem
  23. 5th April (2 classes): Toda's theorem continued, Derandomization: error-reduction using expanders (deterministic) (Ref
  24. )
  25. 9th April: Probabilistic error reduction using expanders Ref
  26. 11th April (extra class):Pseudorandomness: PRG for space-bounded computation: INW generator (Ref
  27. 12th April: Parity not in AC0 (Ref)
  28. 16th April: Parity not in AC0 continued, Undirected s-t connectivity in logspace (Ref)

Top