Time: MW 14:00-15:30
Location: A-212
Instructor:
Homepage:
http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/complexity
Course Calendar (Subcribe to the calendar (ical format))
6 Feb | 1. Introduction to computational complexity Administrivia, efficient computation, Turing machine, Universal Turing machine (UTM), efficient simulation by UTMs. Ref: [ AB (Chap. 1), vM (Lec. 1 & 2) ] |
8 Feb | 2. NP and NP completeness (part I) Review of efficient UTM simulation; classes P, NP; polynomial time reductions; NP-completeness. Ref: [ AB (Chap. 2) ] |
13 Feb | 3. NP and NP Completeness (part II) Non-determinisim; Cook-Levin Theorem, parsimonious reductions, search vs. decision problems, coNP Ref: [ AB (Chap. 2) ] |
15 Feb | 4. Diagonalization (part I) time hierarchy theorem (deterministic and non-deterministic), limits of diagonalization (Baker-Gill-Solovay theorem). Ref: [ AB (Chap. 3) ] |
20 Feb | 5. Diagonalization (part II) limits of diagonalization (Baker-Gill-Solovay theorem), NP-intermediate problems (Ladner's Theorem). Ref: [ AB (Chap. 3), For1 ] |
22 Feb | 6. Space Complexity (part I) space as a resouce, configuration graphs, TQBF, PSPACE completeness, PSPACE=NPSPACE. Ref: [ AB (Chap. 4) ] |
1 Mar | 7. Space Complexity (part II) Savitch's theorem, logspace reductions, NL-completeness, certificate complexity, NL=coNL (Immerman-Szelepcsyéni Theorem). Ref: [ AB (Chap. 4) ] |
7 Feb | 8. Alternation and Polynomial hierarchy Classes ΣP,ΠP, polynomial time hierarchy, alternating machines. Ref: [ AB (Chap. 5), Sud (Lec. 3) ] |
5 Mar | 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) ] |
7 Mar | 10. Boolean circuits Karp-Lipton-Sipser Theorem, Meyer's Theorem circuit lower bounds discussion. Ref: [ AB (Chap. 6) ] |
12 Mar | 11. Randomized computation (part I) bounded depth circuit classes, randomized algorithms (primality, PIT, perfect matching), probabilistic complexity classes Ref: [ AB (Chap. 6, 7) ] |
14 Mar | 12. Randomized computation (part II) Error reduction by amplification, BPP ⊂ P/poly, BPP ⊂ PH, randomized space. Ref: [ AB (Chap. 7) ] |
19 Mar | 13. Complexity of counting (part I) promise problems, Unique-SAT (Valiant Vazirani), #P, PP, #P-completeness. Ref: [ AB (Chap. 17), Vad (Lec 12 & 13) ] |
21 Mar | 14. Complexity of Counting (part II) Valiant's Theorem: #P-completeness of permanent Ref: [ AB (Chap. 17), DHW (gadgets for Valiant's theorem taken from Figure 2 on page 8) ] |
26 Mar | 15. Complexity of Counting (part III) PP, ⊕P, Toda's Theorem (part 1: PH ⊂ BP.⊕P) Ref: [ AB (Chap. 17), Sud (Lec. 10 & 11) ] |
31 Mar | 16. Complexity of Counting (part IV) Toda's Theorem (part 2: BP.⊕P ⊂ P,#P), approximate counting. Ref: [ AB (Chap. 17), Sud (Lec. 11), Tre (Chap. 8) ] |
2 Apr | 17. Average case complexity Approximate counting & sampling (conclude), average case complexity: polynomial reconstruction, permanent. Ref: [ AB (Chap. 17), Tre (Chap. 8), Vad (Lec. 16) ] |
4 Apr | 18. Interactive proofs (part I) what is a proof?, interactive proofs, graph non-isomorphism, P#P ⊂ IP. Ref: [ AB (Chap. 8), Vad (Lec. 17) ] |
9 Apr | 19. Interactive proofs (part II) IP=PSPACE, power of prover, program checking/correcting. Ref: [ AB (Chap. 8), Vad (Lec. 18) ] |
18 Apr | 20. Interactive proofs (part III) Arthur-Merlin games, Public Coins = Private Coins, Round reduction for AM, GI - NP-complete? Ref: [ AB (Chap. 8), Vad (Lec. 18 & 19) ] |
19 Apr | 21. PCPs and hardness of approximation (part I) IP Extensions IP - MIP, PCP; PCP Theorem; approximability; two views (proof checking and inapproximability). Ref: [ AB (Chap. 11), Har1 (Lec. 4), Vad (Lec. 20) ] |
21 Apr | 22. PCPs and hardness of approximation (part II) Equivalence of two view of PCP Theorem (proof checking and inapproximability), inapproximability of Clique (FGLSS reduction). Ref: [ AB (Chap. 11), Har1 (Lec. 4), Vad (Lec. 20) ] |
23 Apr | 23. Linearity Testing BLR linearity testing: combinatorial analysis for general groups and Coppersmith's example; NP ⊂ PCP[poly(n), O(1)]. Ref: [ AB (Chap. 11), Har1 (Lec. 5) ] |
25 Apr | 24. Exponential sized constant query PCPs for NP Proof of NP ⊂ PCP[poly(n), O(1)] based on linearity testing and Frievald's matrix multiplication test [ALMSS]. Ref: [ AB (Chap. 11), Har2 (Lec. 4) ] |
30 Apr | 25. Fourier analysis Introduction to Fourier analysis; applications to linearity testing, resilient functions. Ref: [ Har1 (Lec. 6), CGHFRS (Lemma 7) ] |
2 May | 26. ε-biased sample spaces and Cayley
expanders ε-biased sample spaces (definition, probabilistic construction and explicit construction). Ref: [ Gol (Lec. 7 & 8), Zuc (Lec. 7) ] expanders (definition, spectral expansion), Cayley expanders (relation to ε-biased sets). Ref: [ DH (Lec. 2), For2 ] |
7 May | 27. Proof Complexity (part I) Intro. to proof complexity, relation to NP=coNP, different proof systems, resolution. Ref: [ AB (Chap. 15), Tre (Chap. 21) ] |
9 May | 28. Proof Complexity (part II) Resolution: short proofs imply narrow proofs (BenSasson-Wigderson). Ref: [ Tre (Chap. 21 & 22) ] |
11 May | 29. Proof Complexity (part III) Width lower bounds for random k-CNFs and pigeon-hole principle. Ref: [ Tre (Chap. 22) ] |
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 ] |
[CGHFRS] | Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedmann, Steven Rudich and Roman Smolensky. The Bit Extraction Problem or t-Resilent Functions. In Proc. 26th. FOCS, pages 396-407, 1985. [ DOI ] |
[DH] | Cynthia Dwork and Prahladh Harsha. CS369E: Expanders in Computer Science. A course offered at Stanford (Spring 2005), [ .html ] |
[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 ] |
[For1] | Lance Fortnow. Two proofs of Ladner's Theorem Blogpost, Computational Complexity Blog, 24 Mar 2003. [ .html | .pdf ] |
[For2] | Lance Fortnow. Expanders from Epsilon-Biased Sets Blogpost, Computational Complexity Blog, 30 Jun 2003. [ .html ] |
[Gol] | Oded Goldreich. Randomized Methods in Computation, 2001. A course offere at Weizmann Institute of Science. [ .html ] |
[Har1] | Prahladh Harsha. Limits of approximation algorithms, 2010. A course offered at TIFR & IMSc (Spring 2010). [ .html ] |
[Har2] | Prahladh Harsha. CMSC 39600: PCPs, codes and inapproximability, 2007. A course offered at Univ. Chicago (Autumn 2007). [ .html ] |
[vM] | 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 ] |
[Zuc] | David Zuckerman. CS 395T - Pseudorandomness and Combinatorial Constructions. A course offered at UT, Austin (Spring 2001). [ .html ] |
This page has been accessed at least times since 30 January, 2012.
Prahladh Harsha |