Time: Tu 16:00-17:30 and Th 14:00-15:30
Location: A201
Instructor:
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2017-18/complexity
16 Jan | 1. Introduction to computational complexity Administrivia; problems of interest: connectivity, matching, SAT, CNF-minimization, permanent, PIT; Turing machine Ref: [ AB (Chap. 1), Sud2 (Lec. 1)] |
23 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)] |
25 Jan | 3. NP and NP Completeness (part II) Cook-Levin Theorem, web of reductions, decision vs. search, downward self-reducibility of SAT. Ref: [ AB (Chap. 2) ] |
30 Jan | 4. Diagonalization (part I) coNP, NP vs. coNP problem; diagonalization: time hierarchy theorem (deterministic and non-deterministic). Ref: [ AB (Chap. 2-3) ] |
1 Feb | 5. Diagonalization (part II) non-deterministic time hierarchy, oracle TMs, relativization, limits of diagonalization (Baker-Gill-Solovay theorem) Ref: [AB (Chap.3) ] |
6 Feb | 6. Space Complexity (part I) space as a resouce, configuration graphs, TQBF, PSPACE completeness Ref: [ AB (Chap. 4) ] |
8 Feb | 7. Space Complexity (part II) Savitch's theorem, logspace reductions, NL-completeness, NL=coNL (Immerman-Szelepcsyéni Theorem) Ref: [ AB (Chap. 4) ] |
13 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) ] |
14 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) ] |
20 Feb | 10. Boolean circuits (Lecturer: Ramprasad
Saptharishi) Boolean circuits, P/poly, complexity classes with advice, Karp-Lipton-Sipser Theorem, Meyer's Theorem. Ref: [ AB (Chap. 6) ] |
22 Feb | 11. Randomized computation (part I) circuit lower bounds, bounded depth circuit classes; randomized algorithms: primality (Solovay-Strassen), BPP Ref: [ AB (Chap. 6, 7), ISGS (Lec 5-6) ] |
27 Feb | 12. Randomized computation (part II) polynomial identity testing, RP and BPP error reduction, Chernoff bounds Ref: [ AB (Chap. 7) ] |
1 Mar | 13. Randomized computation (part III) BPP ⊂ P/poly, BPP ⊂ PH Ref: [ AB (Chap. 7) ] |
13 Mar | 14. Barrington's Theorem Branching programs, group programs, Barrington's theorem Ref: [ Vio (Lec 11) ] |
15 Mar | 15. Complexity of counting (part I) promise problems, Unique-SAT (Valiant Vazirani), Complexity of counting, #P Ref: [ AB (Chap. 17), Vad (Lec. 13 (Mar 10)), Sud2 (Lec. 9) ] |
20 Mar | 16. Complexity of Counting (part II) #P, FP, PP, #P-completeness, Valiant's theorem: perm is #P-complete. Ref: [ AB (Chap. 17), Vad (Lec. 14 (Mar 22)) Gadgets for Valiant's theorem taken from DHW, See Bla (Fig. 1,2,4 and 5)] |
22 Mar | 17. Complexity of Counting (part III) |
27 Mar | 18. Complexity of Counting (part IV) |
29 Mar | No class (Mahavir Jayanti) |
3 Apr | 19. Interactive proofs (part I) ; PSET 5 (out: 3 Apr, due: 17 Apr) |
5 Apr | 20. Interactive proofs (part II) |
10 Apr | 21. Interactive proofs (part III) |
12 Apr | 22. Interactive proofs (part IV) |
17 Apr | 23. PSET 6 (out: 17 Apr, due: 1 May) |
19 Apr | 24. |
24 Apr | 25. |
26 Apr | 26. |
1 May | 27. |
3 May | 28. |
8 May | 29. |
10 May | 30. |
14 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 ] |
[Bla] | Markus Blaser. Noncommutativity Makes Determinants Hard. In Proc. 40th ICALP (Part I), pages 172-183, 2013. [ DOI ] |
[DHW] | Holger Dell, Thore Husfeldt and Martin Wahlen. Exponential Time Complexity of the Permanent and the Tutte Polynomial. In Proc. 37th ICALP (Part I), pages 426-437, 2011. [ DOI | eccc ] |
[ISGS] | Hiroshi Imai, Tetsuo Shibuya, François Le Gall and Christian Sommer. Advanced Algorithms, 2010. A course offered at the Univ. Tokyo (Summer 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 ] |
[Vad] | Salil Vadhan. CS221: Computational Complexity Theory, 2010 A course offered at Harvard (Spring 2010). [ .html ] |
[Vio] | Emanuele Viola. CS G399: Gems of Theoretical Computer Science, 2009. A course offered at North Eastern University (Spring 2009). [ .html ] |
This page has been accessed at least times since 22 January, 2018.
Prahladh Harsha |