Computational Complexity

Computational Complexity - Winter/Summer Semester (2012-13)

Time: Tue 09:30-11:00, Thu: 11:30-13:00
Location: A-212
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2012-13/complexity

Course Announcement

Course Calendar (Subcribe to the calendar (ical format))

Problem Sets and Exams

PS1 [ pdf (out: 22 Jan, due: 5 Feb) ]
PS2 [ pdf (out: 5 Feb, due: 19 Feb) ]
PS3 [ pdf (out: 20 Feb, due: 6 Mar) ]
Mid-term exam [ pdf (out: 15 Mar, due: 19 Mar) ]
PS4 [ pdf (out: 28 Mar, due: 11 Apr) ]
PS5 [ pdf (out: 18 Apr, due: 30 Apr) ]

Lectures

15 Jan	1. Introduction to computational complexity Administrivia, efficient computation, Turing machine, Universal Turing machine (UTM), efficient simulation by UTMs. Ref: [ AB (Chap. 1) ]
17 Jan	2. Efficient computation Review of efficient UTM simulation, uncomputability; class P Ref: [ AB (Chap. 1) ]
22 Jan	3. NP and NP Completeness (part I) NP, non-determinisim, polynomial time reductions, NP-completeness. Ref: [ AB (Chap. 2) ]
24 Jan	4. NP and NP Completeness (part II) Cook-Levin Theorem, web of reductions, decision vs. search, downward self-reducibility of SAT. Ref: [ AB (Chap. 2) ]
29 Jan	5. Diagonalization (part I) coNP, NP vs. coNP problem; diagonalization: time hierarchy theorem (deterministic and non-deterministic). Ref: [ AB (Chap. 2-3) ]
31 Jan	6. Diagonalization (part II) limits of diagonalization (Baker-Gill-Solovay theorem), NP-intermediate problems (Ladner's Theorem). Ref: [ AB (Chap. 3), vMel (Lecture 5) ]
5 Feb	7. Space Complexity (part I) Ladner's them (complete), space as a resouce, configuration graphs, TQBF, PSPACE completeness. Ref: [ vMel (Lecture 5) , AB (Chap. 4) ]
7 Feb	8. Space Complexity (part II) PSPACE completeness, Savitch's theorem, logspace reductions, NL-completeness. Ref: [ AB (Chap. 4) ]
12 Feb	9. Polynomial hierarchy and alternation (part I) certificate complexity, NL=coNL (Immerman-Szelepcsyéni Theorem), Classes Σ^P,Π^P, polynomial time hierarchy. Ref: [ AB (Chap. 5), Sud (Lec. 3) ]
19 Feb	10. Time-space tradeoffs for SAT polynomial hierarchy, alternating machines, alernating space vs. time, Fortnow's time-space tradeoff theorem. Ref : [ AB (Chap. 5,6), Sud (Lec. 5) ]
21 Feb	11. Polynomial hierarchy and alternation (part II) time-space tradeoff theorem, alternating time vs. space, polynomial hierarchy via oracles. Ref: [ AB (Chap. 5), Sud (Lec. 3) ]
26 Feb	12. Boolean circuits Boolean circuits, P/poly, complexity classes with advice, Karp-Lipton-Sipser Theorem, Meyer's Theorem. Ref: [ AB (Chap. 6) ]
28 Feb	13. Randomized computation (part I) bounded depth circuit classes, circuit lower bounds discussion, randomized algorithms for primality (Solovay-Strassen) Ref: [ AB (Chap. 6, 7) ]
1 Mar	14. Randomized computation (part II) polynomial identity testing, PIT based algorithm for matching, RP error reduction by amplification. Ref: [ AB (Chap. 7) ]
12 Mar	15. Randomized computation (part III) BPP error reduction by amplification, BPP ⊂ P/poly, BPP ⊂ PH, randomized space. Ref: [ AB (Chap. 7) ]
14 Mar	16. Complexity of counting (part I) promise problems, Unique-SAT (Valiant Vazirani) Ref: [ AB (Chap. 17)
19 Mar	17. Complexity of Counting (part II) #P, FP, PP, #P-completeness, Valiant's Theorem: #P-completeness of permanent Ref: [ AB (Chap. 17) ]
21 Mar	18. Complexity of Counting (part III) Valiant's theorem: perm is #P-complete, Toda's Theorem, operators. Ref: [ AB (Chap. 17), DHW (gadgets for Valiant's theorem taken from Figure 2 on page 8), Sud (Lec. 10) ]
28 Mar	19. Complexity of Counting (part IV) Toda's Theorem (part 1: PH ⊂ BP.⊕P) Toda's Theorem (part 2: BP.⊕P ⊂ P^#P). Ref: [ AB (Chap. 17), Sud (Lec. 10-11) ]
2 Apr	20. Approximate counting Approximate counting is in BPP^NP, average case complexity: permanent reconstruction Ref: [ Tre2 (Chap. 8-9) ]
4 Apr	21. Interactive proofs (part I) permanent reconstruction (contd); what is a proof?, interactive proofs, graph non-isomorphism. Ref: [ Tre2 (Chap. 9), Vad (Lec. 17) ]
11 Apr	22. Interactive proofs (part I) interactive proofs, P^#P ⊂ IP. Ref: [ Vad (Lec. 17) ]
12 Apr	23. Interactive proofs (part III) PSPACE ⊂ IP, Arthur-Merlin games. Ref: [ AB (Chap. 8), Vad (Lec. 18 & 19) ]
16 Apr	24. Interactive proofs (part IV) Arthur-Merlin games, Public Coins = Private Coins, Round reduction for AM, GI - NP-complete? Ref: [ AB (Chap. 8), Vad (Lec. 18 & 19) ]
19 Apr	25. Cryptography (part I) Introduction, private key encryption, one-time pad, pseudorandomness, one-way functions. Ref: [ AB (Chap. 9), Tre1 (Lec. 11 & 12) ]
23 Apr	26. Cryptography (part II) examples of OWF/OWP, hardcore predicate, OWP with hardcore predicate implies PRG (with 1-bit stretch). Ref: [ BG (Sec. 2.3-2.4), Tre1 (Lec. 12) ]
25 Apr	27. Cryptography (part III) PRGs with polynomial stretch, PRGs imply derandomization, hardcore bit theorem (Goldreich-Levin). Ref: [ Han (Lec. 21, Sec. 1-2), Tre1 (Lec. 13) ]
30 Apr	28. Cryptography (part IV) hardcore bit theorem (Goldreich-Levin), pseudorandom functions Ref: [ Han (Lec. 21, Sec. 1-2), Tre1 (Lec. 14 & 13.2) ]
2 May	29. Cryptography (part V) pseudorandom function family, GGM construction, application to private key cryptography. Ref: [ Tre3 (Lec. 14), Tre1 (Lec. 13.3) ]

Tentative schedule (for future lectures)

Cryptography & Pseudorandomness (5 lectures)
PSET 6 (out: 25 Apr, due: 9 May)
PCPs and hardness of approximation (2 lectures)
Final exam (14 May)

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
Grading:
- Problems Sets - 50% (best 5 of 6 psets will contribute towards grade)
- Take-home midterm exam - 25%
- Final Exam - 25%

References

[AB]	Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. [ .html ]
[BG]	Mihir Bellare and Shafi Goldwasser. Lecture Notes on Cryptography. Summer course offered at MIT (1996-2008). [ .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 ]
[Han]	Kristoffer Arnsfelt Hansen. CT10: Computational Complexity, Fall 2010. A course offered at Aarhys University (Fall 2010). [ .html ]
[vMel]	Dieter van Melkebeek. CS710: Computational Complexity, 2010. A course offered at Univ. Wisconsin-Madison (Fall 2010). [ .html ]
[Sud]	Madhu Sudan. 6.841/18.405J Advanced Complexity Theory, 2010. A course offered at MIT (Spring 2003). [ .html ]
[Tre1]	Luca Trevisan. CS 278 Computational Complexity, 2001. A course offered at UC, Berkeley (Spring 2001). [ .pdf ]
[Tre2]	Luca Trevisan. CS 278 Computational Complexity, 2002. A course offered at UC, Berkeley (Fall 2002). [ .pdf ]
[Tre3]	Luca Trevisan. CS 276 Cryptography, 2009. A course offered at UC, Berkeley (Spring 2009). [ .html ]
[Vad]	Salil Vadhan. CS221: Computational Complexity Theory, 2010 A course offered at Harvard (Spring 2010). [ .html ]

Previous avatars of this course: 2011, 2012

This page has been accessed at least times since 11 January, 2013.

Prahladh Harsha