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


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. new


Problem Sets and Exams

  1. PS1 [ pdf (out: 16 Jan, due: 30 Jan) ]
  2. PS2 [ pdf (out: 13 Feb, due: 27 Feb) ]
  3. PS3 [ pdf (out: 3 Mar, due: 17 Mar) ]
  4. PS4 [ pdf (out: 14 Apr, due: 28 Apr) ]
  5. PS5 [ pdf (out: 7 May, due: 21 May) ]

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

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

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

This page has been accessed at least Counter times since 9 January, 2020.


Prahladh Harsha
Valid HTML 4.01! Valid CSS!