Time: Tue-Thu 11:30-13:00
Location: A201
Instructor:
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2019-20/complexity
14 Jan | 1. Introduction to computational complexity Administrivia; problems of interest: GCD, primality, connectivity, matching, determinant, SAT, #SAT, CNF-minimization, permanent, PIT; Turing machines Ref: [ AB (Chap. 1), Sud2 (Lec. 1)] |
16 Jan | 2. NP and NP Completeness (part I) Universal TM simulation, Classes P and NP, non-determinisim, polynomial time reductions, NP-completeness. Ref: [ AB (Chap. 2)] |
21 Jan | 3. NP and NP Completeness (part II) Cook-Levin Theorem, web of reductions, decision vs. search, downward self-reducibility of Ref: [ AB (Chap. 2) ] |
23 Jan | 4. Diagonalization (part I) decision vs. search, downward self-reducibility of SAT, coNP, NP vs. P, NP vs. coNP; diagonalization: time hierarchy theorems (deterministic and non-deterministic). Ref: [ AB (Chap. 2-3) ] |
28 Jan | 5. Diagonalization (part II) non-deterministic time hierarchy, oracle TMs, relativization, limits of diagonalization (Baker-Gill-Solovay theorem); Space complexity, configuration graphs. Ref: [AB (Chap. 3-4) ] |
30 Jan - 11 Feb: No class | |
13 Feb | 6. Space Complexity (part I) TQBF, PSPACE completeness, Savitch's theorem, logspace reductions, NL-completeness Ref: [ AB (Chap. 4) ] |
14 Feb | 7. Space Complexity (part II) Certificate viewpoint of NL, NL=coNL (Immerman-Szelepcsyéni Theorem) Ref: [ AB (Chap. 4) ] |
18 Feb | 8. Polynomial hierarchy and alternation (part I) NL=coNL; Classes Σ^{P},Π^{P}, polynomial time hierarchy, three definitions (predicates, alternating TMs, oracle TMs) Ref: [ AB (Chap. 4-5) ] |
20 Feb: No class | |
25 Feb | 9.Polynomial hierarchy and alternation (part II) Alternating TMS, alernating space vs. time, Fortnow's time-space tradeoff theorem. Ref : [ Sud1 (Lec. 3 and 5) ] |
27 Feb | 10. Boolean circuits |
3 Mar | 11. Randomized computation (part I) |
PSET 3 (out: 3 Mar, due: 17 Mar) | |
5 Mar | 12. Randomized computation (part II) |
10 Mar | No class (Holi) |
12 Mar | 13. Randomized computation (part III) |
17 Mar | 14. Barrington's Theorem |
MIDTERM (out: 19 Mar, due: 23 Mar) | |
19 Mar | 15. Complexity of counting (part I) |
24 Mar | 16. Complexity of Counting (part II); |
PSET 4 (out: 24 Mar, due: 7 Apr) | |
26 Mar | 17. Complexity of Counting (part III) |
31 Mar | 18. Complexity of Counting (part IV) |
2 Apr | 19. Approximate Counting |
7 Apr | 20. Interactive proofs (part I) |
9 Apr | 21. Interactive proofs (part II) |
PSET 5 (out: 9 Apr, due: 28 Apr) | |
14 Apr | 22. Interactive proofs (part III) |
16 Apr | 23. Interactive proofs (part IV) |
21 Apr | 24. PCPs and Hardness of Approximation (part I) |
23 Apr | 25. PCPs and Hardness of Approximation (part II) |
28 Apr | 26. Advanced Topics (TBD) |
30 Apr | 27. Advanced Topics (TBD) |
PSET 6 (out: 30 Apr, due: 14 May) | |
5 May | 28. Advanced Topics (TBD) |
7 May | No class (Buddha Purnima) |
12 May | 29. Advanced Topics (TBD) |
14 May | 30. Advanced Topics (TBD) |
19 May | FINAL EXAM |
Students taking the course for credit will be expected to:
[AB] | Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. [ .html ] |
[Han] | Kristoffer Arnsfelt Hansen. CT10: Computational Complexity, Fall 2010. A course offered at Aarhys University (Fall 2010). [ .html ] |
[vMel] | Dieter van Melkebeek. CS710: Computational Complexity, 2010. A course offered at Univ. Wisconsin-Madison (Fall 2010). [ .html ] |
[Sud1] | Madhu Sudan. 6.841/18.405J Advanced Complexity Theory, 2003. A course offered at MIT (Spring 2003). [ .html ] |
[Sud2] | Madhu Sudan. 6.841/18.405J Advanced Complexity Theory, 2007. A course offered at MIT (Spring 2007). [ .html ] |
[Tre] | Luca Trevisan. CS 278 Computational Complexity, 2002. A course offered at UC, Berkeley (Fall 2002). [ .pdf ] |
[Vad1] | Salil Vadhan. CS221: Computational Complexity Theory, 2010 A course offered at Harvard (Spring 2010). [ .html ] |
This page has been accessed at least times since 9 January, 2020.
Prahladh Harsha |