Time: MWF 11:00-12:30

Location: A-212 @ TIFR

Instructor:

Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2010-11/complexity

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

- 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**]

12 Jan |
1. Introduction to computational complexityAdministrivia, Computation, Turing Machine, Universal Turing machine (UTM), the class P, efficient simulation by UTMs. Ref: [ AB (Chap. 1) ] |

13 Jan |
2. NP and NP completenessReview of efficient UTM simulation, oblivious UTMs, NP, Karp reductions, NP-completeness. Ref: [ AB (Chap. 2) ] |

14 Jan |
3. NP CompletenessCook-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 hierarchyClasses ΣP,ΠP, polynomial time hierarchy, alternating space and time. Ref: [ AB (Chap. 5), Sud (Lec. 3) ] |

9 Feb |
9. Time-space tradeoffs and Boolean circuitsFortnow'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
classesKarp-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 computationBPP ⊂ 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 approximationExtensions 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
amplificationInapproximability 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 LemmaYao'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 boundsImpagliazzo-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^{0}Circuit classes (NC ^{i}, AC^{i}), parity not in
AC^{0} 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^{0}Proof of Switching Lemma Ref: [ AB (Chap. 14), Bea, Sud (Lec. 8) ] |

2 May |
31. Circuit lower bounds (part III): ⊕ ∉
AC^{0}parity not in AC ^{0} using polynomials
(Razborov-Smolensky).Ref: [ (Chap. 14) ] |

2 May |
32. Concluding lectureConclusion, review of topics covered and not covered! |

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%

**[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 |