Computational Complexity

Computational Complexity - Spring Semester (2010-11)

Time: MWF 11:00-12:30
Location: A-212 @ TIFR
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2010-11/complexity

Course Announcement

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

Problem Sets and Exams

Problem Set 1 [ pdf ] [Out: 14 January, 2011; Due: 28 January, 2011]
Problem Set 2 [ pdf ] [Out: 2 February, 2011; Due: 16 February, 2011]
Problem Set 3 [ pdf ] [Out: 16 February, 2011; Due: 28 February, 2011]
Mid-semester Exam [ pdf ] [Out: 9 March, 2011; Due: 11 March, 2011, 18:00]
Problem Set 4 [ pdf ] [Out: 11 March, 2011; Due: 28 March, 2011]
Problem Set 5 [ pdf ] [Out: 7 April, 2011; Due: 20 April, 2011]
Problem Set 6 [ pdf ] [Out: 23 April, 2011; Due: 9 May, 2011]

Course Schedule

12 Jan	1. Introduction to computational complexity Administrivia, Computation, Turing Machine, Universal Turing machine (UTM), the class P, efficient simulation by UTMs. Ref: [ AB (Chap. 1) ]
13 Jan	2. NP and NP completeness Review of efficient UTM simulation, oblivious UTMs, NP, Karp reductions, NP-completeness. Ref: [ AB (Chap. 2) ]
14 Jan	3. NP Completeness Cook-Levin Theorem, parsimonious reductions, search vs. decision problems, downward self-reducibility of SAT, coNP Ref: [ AB (Chap. 2) ]
17-26 Jan	No class (Metric Embeddings and inapproximability workshop and Republic Day (26 Jan))
27 Jan	4. Diagonalization (part I) time hierarchy theorem (deterministic and non-deterministic), limits of diagonalization (Baker-Gil-Solovay theorem). Ref: [ AB (Chap. 3) ]
28 Jan	5. Diagonalization (part II) limits of diagonalization (Baker-Gill-Solovay theorem), NP-intermediate problems (Ladner's Theorem). Ref: [ AB (Chap. 3) ]
31 Jan	No class (Arnab Bhattacharya's talk)
2 Feb	6. Space Complexity (part I) space as a resouce, configuration graphs, TQBF, PSPACE completeness, PSPACE=NPSPACE. Ref: [ AB (Chap. 4) ]
4 Feb	7. Space Complexity (part II) Savitch's theorem, logspace reductions, NL-completeness, PATH, NL=coNL (Immerman-Szelepcsyéni Theorem). Ref: [ AB (Chap. 4) ]
7 Feb	8. Alternation and Polynomial hierarchy Classes ΣP,ΠP, polynomial time hierarchy, alternating space and time. Ref: [ AB (Chap. 5), Sud (Lec. 3) ]
9 Feb	9. Time-space tradeoffs and Boolean circuits Fortnow's time-space tradeoff theorem, Boolean circuits, P/poly, complexity classes with advice. Ref : [ AB (Chap. 5,6), Sud (Lec. 5) ]
11 Feb	10. Boolean circuits and probabilistic complexity classes Karp-Lipton-Sipser Theorem, circuit lower bounds discussion, probabilistic complexity classes (BPP, RP, coRP, ZPP). Ref: [ AB (Chap. 6,7), Tre1 (Lec. 5) ]
16 Feb	11. Probablistic computation BPP ⊂ P/poly, BPP ⊂ PH, randomized algorithms: primality, polynomial identity, perfect matching. Ref: [ AB (Chap. 7) ]
17 Feb	12. Complexity of counting (part I) Unique-SAT (Valiant Vazirani), #P, PP, ⊕P, #P-completeness. Ref: [ AB (Chap. 17) ]
18 Feb	13. Complexity of Counting (part II) Toda's theorem Ref: [ AB (Chap. 17), For, Sud (Lec. 11) ]
21 Feb	14. Complexity of Counting (part III) Permanent - #P-complete (Valiant), approximate counting. Ref: [ AB (Chap. 17), Tre1 (Lec. 8) ]
23 Feb	15. Interactive proofs (part I). Approximate counting (conclude), intro to interactive proofs, graph non-isomorphism, IP[k], AM[k], IP. Ref: [ AB (Chap. 8), Tre1 (Lec. 8) ]
25 Feb	16. Interactive proofs (part II). Public Coins = Private Coins (Goldwasser-Sipser), Round reduction for AM, GI - NP-complete? Ref: [ AB (Chap. 8), Vad (Lec. 19) ]
28 Feb	17. Interactive proofs (part III). AM with perfect completeness, P^#P ⊂ IP (Lund-Fortnow-Karloff-Nisan). Ref: [ AB (Chap. 8) ]
2 Mar	18. Interactive proofs (part IV) IP=PSPACE (Lund-Fortnow-Karloff-Nisan, Shamir), power of the prover in IP. Ref: [ AB (Chap. 8) ]
4 Mar	19. PCPs and hardness of approximation Extensions of IP - MIP, OiP, PCP; approximability; PCP Theorem - two views (proof checking and inapproximability). Ref: [ AB (Chap. 11), Har (Lec. 4) ]
7 Mar	20. Inapproximability and intro to hardness amplification Inapproximability of Clique (FGLSS reduction), power of the prover, hardness amplification. Ref: [ AB (Chaps. 11, 19), Har (Lec. 4) ]
8 Mar	Review session for midterm examination
14 Mar	21. Yao's XOR Lemma Yao's XOR Lemma: sketch of Levin's proof, proof using Impagliazzo's hardcore set lemma. Ref: [ AB (Chap. 19) ]
15 Mar	22. Hardness amplification (part I) Impagliazzo's hardcore set lemma, Goldreich-Levin algorithm. Ref: [ AB (Chaps. 9, 19), Tre2 (Lec. 14) ]
18 Mar-6 Apr	No class (Dagstuhl and Discrete Harmonic Analysis workshops)
8 Apr	23. Derandomization (part I) pseudorandom generators (Blum-Micali, Yao), PRGs towards BPP=P. Ref: [ AB (Chap. 20), Tre1 (Lec. 25) ]
8 Apr	24. Derandomization (part II) Nisan-Wigderson pseudorandom generator Ref: [ AB (Chap. 20), Tre1 (Lec. 26) ]
11 Apr	25. Hardness amplification (part II) worst-case to mildly average-case hard, polynomial reconstruction, primer to coding theory Ref: [ AB (Chap. 19), Tre1 (Lecs. 9, 10) ]
13 Apr	26. Hardness amplification (part III) worst-case to mildly average-case hard, coding theory (code concatenation, unique decoding), STV construction Ref: [ AB (Chap. 19), Tre1 (Lecs. 10, 11) ]
15 Apr	27. Hardness amplification (part IV) worst-case to mildly strongly-case hard, list-decoding (list-decoding (RS codes), local list-decoding (RM, Hadamard codes)), Impagliazzo-Wigderson theorem (E ⊄ SIZE(2^{δ n}) ⇒ BPP=P) Ref: [ AB (Chap. 19), Tre1 (Lecs. 10, 11) ]
15 Apr	28. Derandomization implies circuit lower bounds Impagliazzo-Kabenets-Wigderon (NEXP ⊂ P/poly ⇔ NEXP=MA ), Kabanets-Impagliazzo (PIT ∈ P ⇒ circuit lower bounds) Ref: [ AB (Chap. 19) ]
18 Apr	29. Circuit lower bounds (part I): ⊕ ∉ AC⁰ Circuit classes (NCⁱ, ACⁱ), parity not in AC⁰ using random restrictions (Håstad's switching lemma). Ref: [ AB (Chap. 14), Bea, Tre1 (Lec. 21) ]
20 Apr	30. Circuit lower bounds (part II): ⊕ ∉ AC⁰ Proof of Switching Lemma Ref: [ AB (Chap. 14), Bea, Sud (Lec. 8) ]
2 May	31. Circuit lower bounds (part III): ⊕ ∉ AC⁰ parity not in AC⁰ using polynomials (Razborov-Smolensky). Ref: [ (Chap. 14) ]
2 May	32. Concluding lecture Conclusion, review of topics covered and not covered!

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 (1st edition), Cambridge Universtiy Press, 2009.
[Bea] Paul Beame, A switching lemma primer, Tech. Rep. UW-CSE-95-07-01, Dep. of Comp. Science and Eng., Univ. of Washington, Nov 1994.
[For] Lance Fortnow, A simple proof of Toda's theorem, Theory of Computing, 5(7):135-140, 2009. (DOI: 10.4086/toc.2009.v005a007)
[Har] A course on PCPs and inapproximability (offered by Prahladh Harsha) at TIFR & IMSc: Limits of approximation algorithms (Spring 2009-10).
[Sud] A course on complexity theory (offered by Madhu Sudan) at MIT: 6.841/18.405J Advanced Complexity Theory (Spring 2003).
[Tre1] A course on complexity theory (offered by Luca Trevisan) at UC, Berkeley: CS 278 - Computational Complexity (Fall 2002).
[Tre2] A course on complexity theory (offered by Luca Trevisan) at UC, Berkeley: CS 278 - Computational Complexity (Fall 2004).
[Vad] A course of complexity theory (offered by Salil Vadhan) at Harvard: CS221: Computational Complexity (Spring 2010).

This page has been accessed at least times since 1 January, 2011.

Prahladh Harsha