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]
  3. Introduction to the Theory of Computation by Michael Sipser
    4. [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

Assignment 1 (due on 19th Feb)
Assignment 2 (due on 19th April)
Top

Lectures

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

  1. 2nd 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. 5th Jan: Deterministic turing machines, deterministic time-hierarchy theorem, P-completeness (See this in addition to [AB])

  3. 10th Jan: NP-completeness, Cook-Levin theorem, non-deterministic time-hierarchy theorem (Here is the proof I presented in class.)
  4. 12th Jan: co-NP, existence of NP-intermediate languages: Ladner's theorem, introduction to oracle turing machines (See this for two different proofs of Ladner's theorem, thanks to Bhargav for pointing out this reference.)
  5. 17th Jan: Baker-Gill-Solovay theorem
  6. 19th Jan: Turing reductions, space complexity: basic inclusions, configuration graph, directed reachability is NL-complete, Savitch's theorem
  7. 24th Jan: NL=coNL, PSPACE-completeness, introduction to polynomial hierarchy
  8. 7th Feb: Polynomial hierarchy and its properties
  9. 9th Feb: Circuits: non-uniform and uniform, P/poly, TMs with advice
  10. 11th Feb: Karp-Lipton theorem, Meyer's theorem
  11. 11th Feb: Introduction to Probabilistic Turing machines, BPP, RP and coRP
  12. 14th Feb: Error reduction in BPP, BPP in P/poly, Sipser Gacs theorem
  13. 28th Feb: Interactive proofs: Introduction, examples: graph non-isomorphism, quadratic non-residuosity, IP ⊆ PSPACE
  14. 2nd Mar: Interactive proof for #3SAT
  15. 7th Mar: Interactive proof for QBF, Introduction to public coin proof systems
  16. 9th Mar: AM, MA, MA ⊆ AM, Goldwasser-Sipser set lower bound protocol (AM protocol for graph non-isomorphism) (Some nice references for interactive proofs are here and here
  17. 14th Mar: Can graph isomorphism be NP-complete? Goldwasser-Sipser set lower bound protocol. Introduction to counting: complexity classes #P,PP, P=PP iff #P=FP (See this along with [AB])
  18. 16th Mar: Approximate counting for #P (Ref)
  19. 21st Mar: Toda's theorem: Valiant-Vazirani reduction, randomized reduction from PH to ⊕SAT
  20. 28th Mar: Toda's theorem continued: making the reduction deterministic (References apart from [AB]: this, this, and this)
  21. 3rd Apr: Undirected st-connectivity in RL, introduction to expander graphs, properties and construction (Reference)
  22. 4th Apr: Expander mixing lemma, deterministic error reduction(Reference, See also this)
  23. 6th Apr: Randomness-efficient error reduction using expanders, introduction to pseudorandom generators
  24. 11th Apr: INW generator (Ref)
  25. 13th Apr: Introduction to PCP theorem, relation to inapproximability
  26. 18th Apr: Proof of PCP theorem for exponential-size proofs. (Ref)