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

Course Announcement

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


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:


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 Counter times since 30 January, 2012.


Prahladh Harsha
Valid HTML 4.01! Valid CSS!