Time: TuTh 09:30-11:00
|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) ]
|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.