## Computational Complexity - Winter/Summer Semester (2013-14)

Time: TuTh 09:30-11:00
Location: D405
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2013-14/complexity

#### Problem Sets and Exams

1. PS1 [ pdf (out: 21 Jan, due: 5 Feb) ]
2. PS2 [ pdf (out: 6 Feb, due: 24 Feb) ]
3. PS3 [ pdf (out: 26 Feb, due: 12 Mar) ]
4. Mid-term exam [ pdf (out: 13 Mar, due: 22 Mar) ]
5. PS4 [ pdf (out: 26 Mar, due: 9 Apr) ]
6. PS5 [ pdf (out: 15 Apr, due: 29 Apr) ]
7. PS6 [ pdf (out: 1 May, due: 13 May) ]
8. Final exam (15 May)

#### Lectures

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

#### Tentative schedule (for future lectures)

 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

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

#### Previous avatars of this course: 2011, 2012, 2013

This page has been accessed at least times since 2 January, 2014.