## Computational Complexity - Winter/Summer Semester (2011-12)

Time: MW 14:00-15:30
Location: A-212
Instructor:
Homepage: http://www.tcs.tifr.res.in/~prahladh/teaching/2011-12/complexity

#### Problem Sets and Exams

1. PS1 [ pdf (out: 13 Feb, due: 27 Feb) ]
2. PS2 [ pdf (out: 27 Feb, due: 12 Mar) ]
3. PS3 [ pdf (out: 12 Mar, due: 26 Mar) ]
4. Mid-term exam (out: 6 Apr, due: 9 Apr) ]
5. PS4 [ pdf (out: 9 Apr, due: 23 Apr) ]
6. PS5 [ pdf (out: 23 Apr, due: 7 May) ]
7. PS6 [ pdf (out: 14 May, due: 24 May) ]
8. Final exam (25 May)

#### Lectures

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

#### 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. 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 ]

#### Previous avatars of this course: 2011

This page has been accessed at least times since 30 January, 2012.