- 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
- Computational Complexity by Christos Papadimitriou
- Introduction to the Theory of Computation by Michael Sipser

Top

- Assignments: 20
- Midsem: 20
- Endsem: 40
- Project: 20

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.

Top

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

8,11 Jan: no class

Top