Computational Complexity - Winter/Summer Semester (2019-20)


Time: Tue-Thu 11:30-13:00
Location: A201
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2019-20/complexity


Problem Sets and Exams

  1. PS1 [ pdf (out: 16 Jan, due: 30 Jan) ]
  2. PS2 [ pdf (out: 13 Feb, due: 27 Feb) ]

Lectures

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 ΣPP, 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) ]

Tentative schedule (for future lectures)

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

Requirements

Students taking the course for credit will be expected to:


References

[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 ]

Previous avatars of this course: 2011, 2012, 2013, 2014, 2018

This page has been accessed at least Counter times since 9 January, 2020.


Prahladh Harsha
Valid HTML 4.01! Valid CSS!