Computational Complexity Theory
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.
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.
There are several online lecture notes. I will mention appropriate references
from time to time.
- Computational Complexity: A Modern Approach by Sanjeev Arora, and Boaz Barak
- Computational Complexity by Christos Papadimitriou[CP]
- Introduction to the Theory of Computation by Michael Sipser[MS]
There will be two quizzes, midsem, and endsem.
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.
Assignment 1 (due on 19th Feb)
Assignment 2 (due on 19th April)
Topics covered so far (refer to [AB] unless otherwise mentioned):
- 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.
- 5th Jan: Deterministic turing machines, deterministic time-hierarchy
theorem, P-completeness (See this in addition to [AB])
- 10th Jan: NP-completeness, Cook-Levin theorem, non-deterministic time-hierarchy theorem (Here is the proof I presented in class.)
- 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.)
- 17th Jan: Baker-Gill-Solovay theorem
- 19th Jan: Turing reductions, space complexity: basic inclusions,
configuration graph, directed reachability is NL-complete,
- 24th Jan: NL=coNL, PSPACE-completeness, introduction to polynomial
- 7th Feb: Polynomial hierarchy and its properties
- 9th Feb: Circuits: non-uniform and uniform, P/poly, TMs with advice
- 11th Feb: Karp-Lipton theorem, Meyer's theorem
- 11th Feb: Introduction to Probabilistic Turing machines, BPP, RP and coRP
- 14th Feb: Error reduction in BPP, BPP in P/poly, Sipser Gacs theorem
- 28th Feb: Interactive proofs: Introduction, examples: graph non-isomorphism, quadratic non-residuosity, IP ⊆ PSPACE
- 2nd Mar: Interactive proof for #3SAT
- 7th Mar: Interactive proof for QBF, Introduction to public coin
- 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
- 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])
- 16th Mar: Approximate counting for #P (Ref)
- 21st Mar: Toda's theorem: Valiant-Vazirani reduction,
randomized reduction from PH to ⊕SAT
- 28th Mar: Toda's theorem continued: making the reduction deterministic (References apart from [AB]: this, this, and this)
- 3rd Apr: Undirected st-connectivity in RL, introduction to
expander graphs, properties and construction (Reference)
- 4th Apr: Expander mixing lemma, deterministic error reduction(Reference, See also this)
- 6th Apr: Randomness-efficient error reduction using expanders, introduction to pseudorandom generators
- 11th Apr: INW generator (Ref)
- 13th Apr: Introduction to PCP theorem, relation to inapproximability
- 18th Apr: Proof of PCP theorem for exponential-size proofs. (Ref)