Computational Complexity Theory

• Instructors : Chandan Saha   Course number and Credits : E0 224 and 3:1   Lecture time : Tu,Th 9:30-11:00   Venue : CSA 117


• TA : Vineet Nair


• Objective : Same as last year's course but the syllabus would be a little different.


• Syllabus (tentative):
  • P, NP and NP-completeness
  • Space complexity
  • Polynomial time hierarchy
  • Boolean circuits
  • Randomized computation
  • Introduction to PCP theorem and hardness of approximation
  • Complexity of counting
  • Average-case complexity


• References :
  1. Computational Complexity - A Modern Approach by Sanjeev Arora and Boaz Barak
  (We'll closely follow this book)
  2. Computational Complexity Theory by Steven Rudich and Avi Wigderson (Editors)
  3. Gems of Theoretical Computer Science by Schoening and Pruim
  4. The Nature of Computation by Moore and Mertens
  5. The Complexity Theory Companion by Hemaspaandra and Ogihara
  6. Online lecture notes... (take a look at this webpage)
  
  
• Prerequisites : Basic familiarity with undergraduate level theory of computation and data structures & algorithms would be helpful. More importantly, we expect some mathematical maturity with an inclination towards theoretical computer science.


• Grading policy :
  • Assignments - 30%
  • Mid-term exam - 25%
  • End-term exam - 25%
  • Scribing lecture notes - 20%


• Announcements:
  • Mid-term exam on October 3, 2015 (Saturday). Time: 10:00-13:00. Venue: CSA 117
  • End-term exam on December 8, 2015 (Tuesday). Time: 10:00-13:00. Venue: CSA 117


• Assignments :
  • Assignment 1 (due date: Sep 20, 2015)
  • Assignment 2 (due date: Oct 31, 2015)


• Lectures (mildly edited):
  • Lecture 1: Introduction; Turing machines; Class P and NP
  • Lecture 2: Reductions; NP-completeness; Cook-Levin theorem
  • Lecture 3: Some NP-complete problems
  • Lecture 4: Search versus decision; Class co-NP, EXP; Diagonalization
  • Lecture 5: Oracle Turing machines; Baker-Gill-Solovay theorem
  • Lecture 6: Space complexity: Class PSPACE, L, NL; Savitch's theorem
  • Lecture 7: TQBF is PSPACE-complete; Certificate definition of NL
  • Lecture 8: NL-completeness; NL = co-NL
  • Lecture 9: Polynomial Hierarchy
  • Lecture 10: Polynomial Hierarchy (contd.); Boolean circuits: class P/poly, Karp-Lipton theorem
  • Lecture 11: Boolean circuits: Uniformity, TM with advice, classes NC and AC, circuit lower bounds, P-completeness
  • Lecture 12-13: Parity not in AC0
  • Lecture 14: Class BPP; Schwatz-Zippel lemma, perfect matching in bipartite graphs
  • Lecture 15: Error reduction in BPP; BPP in P/poly; classes RP, co-RP and ZPP
  • Lecture 16: Sipser-Gács theorem; randomized reduction
  • Lecture 17: Goldwasser-Sipser theorem: Graph non-isomorphism in BP.NP
  • Lecture 18: PCP theorem and Hardness of approximation: Intro
  • Lecture 19: PCP contd.: Equivalence of the proof and the gap problem formulations
  • Lecture 20: Hardness of approximation of Max-INDSET and Min-VertexCover; Hadamard codes
  • Lecture 21: NP in PCP(poly(n),1)
  • Lecture 22: BLR linearity test
  • Lecture 23: Counting complexity: Class #P, PP and parity P
  • Lecture 24: #P-completeness
  • Lecture 25: Approximate solutions to #P problems
  • Lecture 26: Toda's theorem: Parity-SAT, Valiant-Vazirani theorem
  • Lecture 27-28: Toda's theorem (contd.)
  • Lecture 29-30: #P-completeness of 0/1 permanent