CSS.203.1: Computational Complexity - Winter/Summer Semester (2020-21)


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


Videos Problem Sets Lectures References

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.


Online Videos of Lectures


Problem Sets and Exams

  1. PS1 [ (out: 17 Feb, due: 3 Mar) ]
  2. PS2 [ (out: 10 Mar, due: 24 Mar) ]
  3. PS3 [ (out: 31 Mar, due: 14 Apr) ]
  4. Mid-term exam [ (out: 23 Apr, due: 28 Apr) ]
  5. PS4 [ (out: 12 May, due: 26 May) ]
  6. PS5 [ (out: 2 Jun, due: 16 Jun) ]

Lectures

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

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

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

This page has been accessed at least Counter times since 12 February, 2021.


Prahladh Harsha