Time: TuTh 09:30-11:00
Location: D405
Instructor:
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2013-14/complexity
16 Jan | 1. Introduction to computational complexity Administrivia, efficient computation, Turing machine, Universal Turing machine (UTM), efficient simulation by UTMs. Ref: [ AB (Chap. 1), Sud (Lec. 1), Tre1 (Chap. 1) ] |
21 Jan | 2. NP and NP Completeness (part I) Classes P, NP, non-determinisim, polynomial time reductions, NP-completeness. Ref: [ AB (Chap. 2), Tre1 (Chap. 1) ] |
23 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), Tre1 (Chap. 1)] |
28 Jan | 4. Diagonalization (part I) coNP, NP vs. coNP problem; diagonalization: time hierarchy theorem (deterministic and non-deterministic). Ref: [ AB (Chap. 2-3) ] |
30 Jan | 5. Diagonalization (part II) limits of diagonalization (Baker-Gill-Solovay theorem), Presentation by Suhail Sherif: NP-intermediate problems (Ladner's Theorem). Ref: [ AB (Chap. 3), vMel (Lecture 5, Sec. 3), For ] |
4 Feb | 6. Space Complexity (part I) (Lecture by Jaikumar Radhakrishnan) space as a resouce, configuration graphs, TQBF, PSPACE completeness, Savitch's theorem Ref: [ vMel (Lecture 5) ] |
6 Feb | 7. Space Complexity (part II) (Lecture by Jaikumar Radhakrishnan) Savitch's theorem, logspace reductions, NL-completeness, NL=coNL (Immerman-Szelepcsyéni Theorem) Ref: [ AB (Chap. 4) ] |
12 Feb | 8. Polynomial hierarchy and alternation (part I)
(substitute lecture instead of 11 Feb) Classes Σ^{P},Π^{P}, polynomial time hierarchy, three definitions (predicates, alternating TMs, oracle TMs) Ref: [ AB (Chap. 5) ] |
13 Feb | No Class (Arithmetic Complexity Workshop) |
18 Feb | 9.Polynomial hierarchy and alternation (part II) Alternation, alernating space vs. time, Fortnow's time-space tradeoff theorem. Ref : [ Sud (Lec. 3 and 5) ] |
20 Feb | 10. Boolean circuits (part I) Boolean circuits, P/poly, complexity classes with advice, Karp-Lipton-Sipser Theorem, Meyer's Theorem. Ref: [ AB (Chap. 6) ] |
27 Feb | 11. Randomized computation (part I) circuit lower bounds, bounded depth circuit classes; randomized algorithms: primality (Solovay-Strassen), bipartite matching, undirected connectivity Ref: [ AB (Chap. 6, 7) ] |
4 Mar | 12. Randomized computation (part II) primality (Solovay-Strassen), probabilistic complexity classes: BPP, RP, coRP and ZPP. Ref: [ AB (Chap. 7) ] |
6 Mar | 13. Randomized computation (part III) RP and BPP error reduction by amplification, BPP ⊂ P/poly, BPP ⊂ PH, randomized space. Ref: [ AB (Chap. 7) ] |
7 Mar | 14. Complexity of counting (part I) (substitute lecture instead of 25 Feb) promise problems, Unique-SAT (Valiant Vazirani) Ref: [ AB (Chap. 17), Sud (Lec. 9) ] |
11 Mar | 15. Complexity of Counting (part II) #P, FP, PP, #P-completeness, Toda's theorem (PH ⊂ P^{#P}) Ref: [ AB (Chap. 17) ] |
13 Mar | 16. Complexity of Counting (part III) Proof of Toda's Theorem (part 1: PH ⊂ BPP^{⊕P}, part 2: BP.⊕P ⊂ P^{#P}). Ref: [ AB (Chap. 17), Sud (Lec. 10-11) ] |
18 Mar - 1 Apr | No Class (Prahladh travelling) |
3 Apr | 17. Complexity of Counting (part IV) Valiant's theorem: perm is #P-complete. Ref: [ AB (Chap. 17), Sal (Lec. 14) Gadgets for Valiant's theorem taken from DHW, See Bla (Fig. 1,2,4 and 5), ] |
4 Apr | 18. Approximate counting Properties of permanent, Approximate counting is in BPP^{NP} Ref: [ Tre2 (Chap. 8-9) ] |
8 Apr | 19. Interactive proofs (part I) what is a proof?, interactive proofs, graph non-isomorphism. Ref: [ Tre2 (Chap. 9), Vad (Lec. 17) ] |
10 Apr | 20. Interactive proofs (part II) interactive proofs, P^{#P} ⊂ IP, program checkability Ref: [ Vad (Lec. 17 & 18) ] |
15 Apr | 21. Interactive proofs (part III) Presentation by Nikhil Mande: PSPACE ⊂ IP; Arthur-Merlin games, public coins= private coins, GI - NP-complete? Ref: [ AB (Chap. 8), Vad (Lec. 18 & 19) ] |
17 Apr | 22. PCPs and hardness of approximation (part I) power of prover, IP Extensions IP - MIP, PCP; PCP Theorem; approximability. Ref: [ AB (Chap. 11), Har (Lec. 4) ] |
22 Apr | 23. PCPs and hardness of approximation (part II) Equivalence of two view of PCP Theorem (proof checking and inapproximability), inapproximability of Clique (FGLSS reduction). Ref: [ Har (Lec. 4) ] |
29 Apr | 24. PCPs and hardness of approximation (part III) 2-query PCPs and Label cover, linearity testing, primer to Fourier analysis. Ref: [ Har (Lec. 5-6) ] |
1 May | 25. PCPs and hardness of approximation (part IV) Linearity testing over GF(2) using Fourier analysis, long code. Ref: [ Har (Lec. 6 and 11) ] |
2 May | 26. PCPs and hardness of approximation (part V) Hastad's 3-bit PCP, Hardness of MAX3LIN2. Ref: [ Har (Lec. 11) ] |
2 May | 26. Hardness of approximation (MAX3LIN2 and Unique Games) |
6 May | 27. Advanced topics - TBD |
8 May | 28. Advanced topics - TBD |
15 May | FINAL EXAM |
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 ] |
[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 ] |
[For] | Lance Fortnow. Two proofs of Ladner's Theorem Blogpost, Computational Complexity Blog, 24 Mar 2003. [ .html | .pdf ] |
[Har] | Prahladh Harsha. Limits of approximation algorithms, 2010. A course offered at TIFR & IMSc (Spring 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 ] |
[Tre] | Luca Trevisan. CS 278 Computational Complexity, 2002. A course offered at UC, Berkeley (Fall 2002). [ .pdf ] |
[Vad] | Salil Vadhan. CS221: Computational Complexity Theory, 2010 A course offered at Harvard (Spring 2010). [ .html ] |
This page has been accessed at least times since 2 January, 2014.
Prahladh Harsha |