Time: Tue-Thu 11:30-13:00
Location: A201 (till Mar 12) / Zoom-based (from Mar 17)
Instructor:
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2019-20/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 starting 17 Mar, 2020. Those who are interested in joining, send me an email by the end of the previous day and I'll share the zoom link to join the online lecture.
The online lectures will be both transcribed and recorded. The online
transcripts are available below as pdfs. If you want access to the
videos, send me email.
| 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 Boolean circuits, P/poly, complexity classes with advice, Karp-Lipton-Sipser Theorem, Meyer's Theorem. Ref: [ AB (Chap. 6) ] |
| 3 Mar | 11. Randomized computation (part I) circuit lower bounds, bounded depth circuit classes; randomized algorithms: primality (Solovay-Strassen), matching, quadratic factorization Ref: [ AB (Chap. 6, 7), MR (Sec 14.6) ] |
| 5 Mar | 12. Randomized computation (part II) primality algorithm (Solovay-Strassen), probabilistic complexity classes: BPP, RP, coRP, ZPP, error reduction. Ref: [ MR (Sec 14.6), AB (Chap. 7) ] |
| 10 Mar: No class (Holi) | |
| 12 Mar | 13. Randomized computation (part III) Error reduction for BPP; Chernoff bound; BPP ⊂ P/poly, BPP ⊂ PH Ref: [ AB (Chap. 7) ] |
| 17 Mar | 14. Barrington's Theorem (Guest Lecturer: Ramprasad
Saptharishi) Branching programs, group programs, Barrington's theorem [ Notes ], Ref: [ Vio (Lec 11) ] |
| 19 Mar | 15. Complexity of counting (part I) promise problems, Unique-SAT (Valiant Vazirani), Complexity of counting, #P [ Notes ], Ref: [ AB (Chap. 17), Vad1 (Lec. 13 (Mar 10)), Sud2 (Lec. 9) ] |
| 24 Mar | 16. Complexity of Counting (part II) #P, FP, PP, #P-completeness, Valiant's theorem: perm is #P-complete. [ Notes ], Ref: [ AB (Chap. 17), Vad1 (Lec. 14 (Mar 22)) Gadgets for Valiant's theorem taken from DHW, See Bla (Fig. 1,2,4 and 5)] |
| 26 Mar: No class | |
| 31 Mar | 17. Complexity of Counting (part III) Valiant's theorem, downward self-reudcibility of Perm, Proof of Toda's Theorem (part 1: PH ⊂ BPP⊕P). [ Notes ], Ref: [ AB (Chap. 17), Vad1 (Lec. 14 (Mar 22)) Gadgets for Valiant's theorem taken from DHW, See Bla (Fig. 1,2,4 and 5), Sud2 (Lec. 12-13) ] |
| 2 Apr | 18. Complexity of Counting (part IV) Proof of Toda's Theorem (part 1: PH ⊂ BPP.⊕.P [ Notes ], Ref: [ AB (Chap. 17), Sud2 (Lec. 12-13) ] |
| 7-9 Apr: No class | |
| 11 Apr | 19. Complexity of Counting (part V) Part 2 of Toda's Theorem: BP.⊕P ⊂ P#P); Approximate counting is in BPPNP [ Notes ], Ref: [ AB (Chap. 17), Sud1 (Lec. 10-11), Sud2 (Lec. 12-13), Tre (Chap. 8) ] |
| 14 Apr | 20. Interactive proofs (part I) Approximate counting is in BPPNP; Introduction to Interactive Proofs, Graph non-isomorphism [ Notes ], Ref: [ Tre (Chap. 8), AB (Chap. 8.1) ] |
| 17 Apr | 21. Interactive proofs (part II) What is a proof?, interactive proofs (formal definition), P#P ⊂ IP (via permanent) [ Notes ], Ref: [ AB (Chap. 8.1 and 8.7) ] |
| 23 Apr | 22. Interactive proofs (part III) IP ⊂ PSPACE; P#P ⊂ IP (via #SAT), extension to TQBF: IP protocol for TQBF. [ Notes ], Ref: [ Vad1 (Lec. 17 & 18), Tre (Lec 14) ] |
| 28 Apr | 23. Interactive proofs (part IV) PSPACE ⊂ IP; Arthur-Merlin protocols, properties of AM protocols, GI - NP-complete? public coins = private coins. [ Notes ], Ref: [ Tre (Lec 14), Vad1 (Lec. 18 & 19) ] |
| 30 Apr | 24. Interactive proofs (part V) Goldwasser-Sipser Theorem: public coins = private coins; multi-prover IP, MIP=NEXP, introduction to PCPs [ Notes ], Ref: [ AB (Chap. 8.2 and 8.5) ] |
| 5 May | 25. PCPs and hardness of approximation (part I) PCP Theorem; approximability, Equivalence of two view of PCP Theorem (proof checking and inapproximability), [ Notes ], Ref: [ AB (Chap. 11), Har2 (Lec. 3-4) ] |
| 7 May | 26. PCPs and hardness of approximation (part II) PCPs and inapproximability, hardness of approximating Clique (FGLSS reduction). [ Notes ], Ref: [ Har2 (Lec. 4) ] |
| 12 May | 27. PCPs and hardness of approximation (part III) Proof of the PCP Theorem: Hadamard codes, Linearity testing, exponential-sized constant-query PCPs for NP, Reed-Muller codes, low-degree testing. [ Notes ], Ref: [ Har1 (Lec. 3-4), Har3 (PCP lectures) ] |
| 14 May | 28. PCPs and hardness of approximation (part IV) Proof of the PCP Theorem: Reed-Muller codes, low-degree testing, zero testing, polynomial-sized polylog-query PCPs for NP. [ Notes ], Ref: [ Har3 (PCP lectures) ] |
| 19 May | 29. Yao's XOR Lemma Hardness Amplification, Yao's XOR Lemma and Levin's proof [ Notes ], Ref: [ Jaikumar's writeup on XOR Lemmax ] |
| 21 May | 30. Goldreich-Levin Theorem Harcore predicates from one-way permutation, Goldreich-Levin Theorem, connection to list-decoding [ Notes ], Ref : [ Luca Trevisan's blogposts (Lec 11, Lec 12) ] |
| 28 May | 26. Hardness Amplification Hardness amplification in E: worst-case hard functions to strongly average-case hard functionsp [ Notes ], Ref: [ Tre (Lec 10), AB (Chap. 19) ] |
| 16 Jun | 32. Derandomization implies Circuit Lower Bounds IKW theorem: NEXP ⊂ P/poly implies NEXP ⊂ MA; Kabanets-Impagliazzo: Consequences of derandomizing PIT; Easy witness method [ Notes ], Ref : [ Bog (Lec 15), TaS (Lec 6), AB (Chap. 20) ] |
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 ] |
| [Bla] | Markus Blaser. Noncommutativity Makes Determinants Hard. In Proc. 40th ICALP (Part I), pages 172-183, 2013. [ DOI ] |
| [Bog] | Andrej Bogdanov. Computational Complexity, 2007. A course offered at ITCS, Tsinghua University (Fall 2007). [ .html ] |
| [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 ] |
| [Har1] | Prahladh Harsha. CMSC 39600: PCPs, codes and inapproximability, 2007. A course offered at Univ. Chicago (Autumn 2007). [ .html ] |
| [Har2] | Prahladh Harsha. Limits of approximation algorithms, 2010. A course offered at TIFR & IMSc (Spring 2010). [ .html ] |
| [Har3] | Prahladh Harsha. Lectures on "Probabilistically Checkable Proofs", Proofs, Consensus, and Decentralizing Society Boot Camp (Aug 26-30), Simons Institute for the Theory of Computing, 2019. [ .html ] |
| [Han] | Kristoffer Arnsfelt Hansen. CT10: Computational Complexity, Fall 2010. A course offered at Aarhys University (Fall 2010). [ .html ] |
| [MR] | Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995. [ doi ] |
| [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 ] |
| [TaS] | Amnon TaShma. 0368.4155 On the P vs. BPP problem, 2017. A course offered atTel-Aviv University (Fall 2017). [ .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 |
|