Schedule: Tue, Fri 3:30-5 pm. LA001.
Office hours: Tue, Fri 5-6 pm. CC315.
Course Contents:
Complexity classes P, NP, co-NP. Polynomial Hierarchy. Space Complexity. Randomization and Pseudorandomness. Circuit lower bounds. Interactive proofs. Probabilistically checkable proofs. Hardness of approximation. Complexity of counting. Error correcting codes. Quantum computation.
Grading: Scribing (5), Assignments (20), Presernations (20), Midsem (20), Endsem (35)
References:
Primary reference Arora and Barak, Computational Complexity: A modern approach.
Goldreich, Computational Complexity: a conceptual perspective
Other useful notes.
Course in TIFR by Prahladh Harsha and Ramprasad Saptharishi
Exercises Assignment 1 Assignment 2
Lecture 4 (Aug 13): Primality is in NP (Pratt's certificate). Nondeterministic TM and NP tex pdf
Lecture 5 (Aug 16): Cook-Levin Theorem, Hamiltonian Path tex pdf
Lecture 6 (Aug 20): NP-hardness reductions, Time hierarchy theorem tex pdf
Lecture 7 (Aug 24): Oracle Turing machines. Padding argument. Max-cut is NP-hard. tex pdf
Lecture 9 (Aug 30): Pspace-completeness, Savitch's theorem tex pdf
Lecture 10 (Sep 3): Rechability is NL-complete. NL=coNL tex pdf
Lecture 13 (Sep 13): TM with advice, classes NC, AC. tex pdf
Lecture 16 (Oct 1): Parity not in AC0. Switching Lemma. tex pdf
Lecture 17 (Oct 4): Probabilistic computation. Primality test. Bipartite matching. tex pdf
Lecture 18 (Oct 8): Polynomial identity testing. Error reduction. BPP is in P/poly. tex pdf
Lecture 20 (Oct 15): PRG from average case hard functions. tex pdf (Unedited)
Lecture 21 (Oct 18): Zero knowledge proofs (by Chethan) slides
Lecture 22 (Oct 22): PRGs for restricted models. Interactive proofs. UNSAT in IP. tex pdf (Unedited)
Lecture 23 (Oct 25): PSPACE in IP. Private coin protocol for GNI.
Lecture 24 (Oct 29): Probabilistically checkable proofs (PCP) and hardness of approximation.