- Assumed background
- Course plan
- References
- Evaluation
- Copying policy
- Assignments and Problem sets
- Lectures

- Computational Complexity: A Modern Approach by Sanjeev Arora, and Boaz Barak Online draft[AB]
- Computational Complexity by Christos Papadimitriou [CP]
- Introduction to the Theory of Computation by Michael Sipser [MS]

Top

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

Assignment 2 (due on 19th April)

Top

- 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, Savitch's theorem
- 24th Jan: NL=coNL, PSPACE-completeness, introduction to polynomial hierarchy
- 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 proof systems
- 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)