Time: Mon-Wed 11:30-13:00
Location: Zoom and Live Youtube Streaming
Instructors: and
Homepage:
http://www.tifr.res.in/~prahladh/teaching/2020-21/complexity
In view of the suspension of all in-class lectures due to the COVID-19 precautionary measure, all classess will be held in the distance model via Zoom.
The online lectures will be both transcribed and recorded. The online transcripts are available below as pdfs while the videos will be available on the STCS TIFR Youtube Channel.
| 15 Feb | 1. Introduction to computational complexity Administrivia; problems of interest: parity, connectivity, matching, SAT, #SAT, CNF-minimization, permanent; Turing machines [ Notes (ph) ], Ref: [ AB (Chap. 1), Sud2 (Lec. 1)] |
| 17 Feb | 2. NP and NP Completeness (part I) Universal TM, Classes P and NP, non-determinism. [ Notes (ph) ], Ref: [ AB (Chap. 2)] |
| 22 Feb | 3. NP and NP Completeness (part II) Polytime Reductions, NP-completeness, web of reductions, Cook-Levin Theorem [ Notes (ph) ], Ref: [ AB (Chap. 2) ] |
| 24 Feb | 4. NP and NP Completeness (part III) Proof of Cook-Levin Theorem, Decision vs Search, downward self-reducibility, coNP, NEXP [ Notes (ph) ], Ref: [ AB (Chap. 2) ] |
| 1 Mar | 5. Diagonalization (part I) decision vs. search, Diagonalization: time hierarchy theorems (deterministic and non-deterministic), Ladner's theorem [ Notes (RS) ], Ref: [ AB (Chap. 2-3) ] |
| 3 Mar | 6. Diagonalization (part II) oracle TMs, relativization, limits of diagonalization (Baker-Gill-Solovay theorem); Space complexity, configuration graphs. [ Notes (RS) ], Ref: [AB (Chap. 3-4) ] |
| 8 Mar | 7. Space Complexity (part I) Space complexity, configuration graphs, PSPACE, TQBF, PSPACE completeness [ Notes (ph) ], Ref: [ AB (Chap. 4) ] |
| 10 Mar | 8. Space Complexity (part II) TQBF is PSPACE-hard, Savitch's theorem, logspace reductions, PATH is NL-complete [ Notes (ph) ], Ref: [ AB (Chap. 4) ] |
| 15 Mar | 9. Polynomial hierarchy (part I) Certificate viewpoint of NL, NL=coNL (Immerman-Szelepcsyéni Theorem) NL=coNL; Classes ΣP,ΠP, polynomial time hierarchy [ Notes 1 (ph), Notes 2 (RS) ], Ref: [ AB (Chap. 4-5) ] |
| 17 Mar | 10. Polynomial hierarchy (part II) polynomial hierarchy, Alternating TMs, alernating space-time vs classical space-time [ Notes (RS) ], Ref: [ AB (Chap. 5) ], Sud1 (Lec. 3) ] |
| 24 Mar | 11. Time-space tradeoffs for SAT Using alternation to prove time-space tradeoffs for SAT, Introduction to Boolean Circuits [ Notes (RS) ], Ref: [ AB (Chap. 5) ], O'D, Sud1 (Lec. 3) ] |
| 26 Mar | 12. Boolean circuits Karp-Lipton and Meyer's theorem, size hierarchy theorem, TMs with advice, a brief introduction to AC and NC classes [ Notes (RS) ], Ref: [ AB (Chap. 6) ] |
| 31 Mar | 13. Randomized computation (part I) randomized algorithms: primality (Solovay-Strassen), matching [ Notes (ph) ], Ref: [ AB (Chap. 7), MR (Sec 14.6) ] |
| 5 Apr | 14. Randomized computation (part II) quadratic polynomial factorization, probabilistic complexity classes: BPP, RP, coRP, ZPP, error reduction. [ Notes (ph) ], Ref: [ AB (Chap. 7) ] |
| 7 Apr | 15. Randomized computation (part III) Error reduction for BPP; Chernoff bound; BPP ⊂ P/poly, BPP ⊂ PH [ Notes (ph) ], Ref: [ AB (Chap. 7) ] |
| 12 Apr | 16. Barrington's Theorem Randomized space; Branching programs, permutation branching programs, Barrington's theorem [ Notes (RS), Sage Notebook ], Ref: [ Vio (Lec 11) ] |
| 19 Apr | 17. Complexity of counting (part I) promise problems, Unique-SAT (Valiant Vazirani), #P [ Notes (RS) ], Ref: [ AB (Chap. 17), Vad1 (Lec. 13 (Mar 10)), Sud2 (Lec. 9) ] |
| 21 Apr | 18. Complexity of Counting (part II) #P-completeness, Valiant's theorem: perm is #P-complete. [ Notes (RS) ], Ref: [ AB (Chap. 17), Vad1 (Lec. 14 (Mar 22)) ] |
| 26 Apr | 19. Complexity of Counting (part III) Toda's Theorem [ Notes (RS) ], Ref: [ AB (Chap. 17), Sud1 (Lec. 11), Har1 (Lec 19) ] |
| 28 Apr | 20. Complexity of Counting (part IV) Approximate counting is in BPPNP, properties of permanent (downward and random self-reducibility) [ Notes (RS) ], Ref: [ AB (Chap. 17), Sud1 (Lec. 10-11), Sud2 (Lec. 12-13), Tre (Chap. 8) ] |
| 3 May | 21. Complexity of Counting (part V) PP, PP vs #P, Beigel-Reingold-Spielman: BPP is closed under intersection [ Notes (RS), Sage Notebook (.html) ] |
| 5 May | 22. Interactive proofs (part I) Introduction to IP, Graph non-isomorphism, P#P ⊂ IP (via permanent) [ Notes (ph) ], Ref: [ AB (Chap. 8.1 and 8.7) ] |
| 10 May | 23. Interactive proofs (part II) P#P ⊂ IP (via permanent), IP ⊂ PSPACE; P#P ⊂ IP (via #SAT) [ Notes (ph) ], Ref: [ AB (Chap. 8.1 and 8.7) ] |
| 12 May | 24. Interactive proofs (part III) P#P ⊂ IP (via #SAT), extension to TQBF: IP protocol for TQBF, Arthur-Merlin protocols, properties of AM protocols [ Notes (ph) ], Ref: [ AB (Chap. 8) ] |
| 17 May | 25. Interactive proofs (part IV) Arthur-Merlin protocols, properties of AM protocols, GI - NP-complete? public coins = private coins. [ Notes (ph) ], Ref: [ AB (Chap. 8) ] |
| 19 May | 26. Zero-knowledge Proof systems (Part I) Zero-knowledge; computational indistinguishability; zero-knowledge for NP; zero-knowledge for all of IP? [ Notes (RS) ], Ref: [ AB (Chap. 8) ] |
| 24 May | 27. Zero-knowledge Proof systems (Part II) Computational zero knowledge for all interactive protocols; proofs of Knowledge and Σ-protocols [ Notes (RS) ] |
| 26 May | 28. PCPs and hardness of approximation (part I) Multiporover interactive proofs (MIP), MIP=NEXP, Probabilistically Checkable Proofs (PCP), The PCP Theorem [ Notes (ph) ], Ref: [ AB (Chap. 11), Har2 (Lec. 3-4) ] |
| 31 May | 29. PCPs and hardness of approximation (part II) Equivalence of two view of PCP Theorem (proof checking and inapproximability) [ Notes (ph) ], Ref: [ AB (Chap. 11), Har2 (Lec. 3-4) ] |
| 2 Jun | 30. PCPs and hardness of approximation (part III) hardness of approximating Clique (FGLSS reduction). [ Notes (ph) ], Ref: [ Har2 (Lec. 4) ] |
| 7 Jun | 31. Parity is not in AC0 Raborovo-Smolensky [ Notes (RS) ] |
| 9 Jun | 32. Concluding Lecture What we did and did not do; feedback |
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 | doi ] |
| [MR] | Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. [ doi ] |
| [Har1] | Prahladh Harsha. Computational Complexity, 2020. A course offered at TIFR (Winter/Summer 2020). [ .html ] |
| [Har2] | Prahladh Harsha. Limits of approximation algorithms, 2010. A course offered at TIFR & IMSc (Spring 2010). [ .html ] |
| [O'D] | Ryan O'Donnell. Graduate Computational Complexity Theory Lecture 9: Time/Space Tradeoffs for SAT. 2017. [ youtube ] |
| [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 ] |
| [Vad1] | 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 12 February, 2021.
| Prahladh Harsha |