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

Time: Tue-Thu 11:30-13:00
Location: A201
Instructor:

#### 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 Σ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) ]

#### 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:

• Do problem sets (approx 1 pset every 2 weeks)
• Give the mid-term and final exams
• Give one presentation