Computational Complexity

Computational Complexity - Winter/Summer Semester (2017-18)

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

Problem Sets and Exams

PS1 [ pdf (out: 23 Jan, due: 6 Feb) ]
PS2 [ pdf (out: 6 Feb, due: 20 Feb) ]
PS3 [ pdf (out: 20 Feb, due: 6 Mar) ]
Mid-term exam [ (out: 8 Mar, due: 13 Mar) ]
PS4 [ pdf (out: 20 Mar, due: 3 Apr) ]
PS5 [ pdf (out: 21 Apr, due: 8 May) ]

Lectures

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), Vad1 (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), Vad1 (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) Valiant's theorem, downward self-reudcibility of Perm, Proof of Toda's Theorem (part 1: PH ⊂ BPP^⊕P). 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) ]
27 Mar	18. Complexity of Counting (part IV) Proof of Toda's Theorem (part 1: PH ⊂ BPP^⊕P, part 2: BP.⊕P ⊂ P^#P) Ref: [ AB (Chap. 17), Sud2 (Lec. 12-13) ]
3 Apr	19. Approximate Counting Approximate counting is in BPP^NP, Interactive proofs, graph-nonisomorphism Ref: [ Tre2 (Chap. 8-9), AB (Chap. 8.1) ]
5 Apr	20. Interactive proofs (part I) what is a proof?, interactive proofs, IP ⊂ PSPACE; P^#P ⊂ IP (via permanent) Ref: [ AB (Chap. 8.2, 8.7) ]
10 Apr	21. Interactive proofs (part II) interactive proofs, P^#P ⊂ IP (via #SAT), extension to TQBF Ref: [ Vad1 (Lec. 17 & 18), Tre (Lec 14) ]
12 Apr	22. Interactive proofs (part III) IP protocol for TQBF, zero-knowledge, Arthur-Merlin games Ref: [ AB (Chap. 8), Vad1 (Lec. 18 & 19), Tre (Lec 14) ]
17 Apr	23. Interactive proofs (part IV) Arthur-Merlin protocols, public coins = private coins, error-reduction for AM protocols, GI - NP-complete? Ref: [ AB (Chap. 8), Vad1 (Lec. 18 & 19) ]
19 Apr	24. PCPs and hardness of approximation (part I) IP Extensions IP - MIP, PCP; proof checking, PCP Theorem; approximability. Ref: [ AB (Chap. 11), Har (Lec. 3-4) ]
24 Apr	25. PCPs and hardness of approximation (part II) (Lecturer: Ramprasad Saptharishi) Equivalence of two view of PCP Theorem (proof checking and inapproximability), inapproximability of Clique (FGLSS reduction). Ref: [ Har (Lec. 4) ]
26 Apr	26. Derandomization (Part I) pseudorandom generators, PRGs towards BPP=P, Hybrid argument Ref : [ Vad2 (Sec 7.1-7.3) ]

Tentative schedule (for future lectures)

1 May	27. Derandomization (Part II)
3 May	28. Derandomization (Part III)
8 May	29. Derandomization (Part IV)
10 May	30. Derandomization (Part V)
11 May	FINAL EXAM

Requirements

Students taking the course for credit will be expected to:

Do problem sets (approx 1 pset every 2 weeks)
Give the mid-term and final exams
Give one presentation
Grading:
- Problems Sets - 50% (best 5 of 6 psets will contribute towards grade)
- Take-home midterm exam - 20%
- Presentation - 5%
- In-class Final Exam - 25%

References

[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 ]
[Har]	Prahladh Harsha. Limits of approximation algorithms, 2010. A course offered at TIFR & IMSc (Spring 2010). [ .html ]
[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 ]
[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 ]
[Vad2]	Salil Vadhan. Pseudorandomness (Monograph). Foundations and Trends in Theoretical Computer Science: Vol. 7: No. 1–3, pp 1-336, now publishers, 2012. [ 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

This page has been accessed at least times since 22 January, 2018.

Prahladh Harsha