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

Course Announcement

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:

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 Counter times since 2 January, 2014.

Prahladh Harsha
Valid HTML 4.01! Valid CSS!