Computational Complexity Theory

• Instructors : Chandan Saha   Course number and Credits : E0 224 and 3:1   Lecture time : M,W 2-3:30 pm   Venue : Google Meet


• Syllabus :
  • P, NP and NP-completeness
  • Space complexity
  • Polynomial time hierarchy
  • Boolean circuits
  • Randomized computation
  • Complexity of counting


• 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. Mathematics and Computation by Avi Wigderson
  4. Boolean Function Complexity by Stasys Jukna
  5. Gems of Theoretical Computer Science by Schoening and Pruim
  6. The Nature of Computation by Moore and Mertens
  7. The Complexity Theory Companion by Hemaspaandra and Ogihara
  8. Online lecture notes... (take a look at this webpage)
  
  
• Prerequisites : Familiarity with undergraduate level data structures & algorithms, and mathematical maturity.


• Grading policy :
  • Assignments - 45%
  • Weekly (online) interactions - 15%
  • Presentation - 20%
  • Final (oral) exam - 20%


• Assignments :
  • Assignment 1 (due date: Nov 15, 2020)
  • Assignment 2 (due date: Dec 15, 2020)
  • Assignment 3 (due date: Jan 15, 2021)


• Lectures :
  • Lecture 1: Introduction; Turing machines; Class P
  • Lecture 2: Class NP; NP-completeness; Cook-Levin theorem
  • Lecture 3: NP-complete problems; Search versus Decision
  • Lecture 4: NTM; Class co-NP and EXP; Diagonalization
  • Lecture 5: Ladner's theorem; Relativization
  • Lecture 6: Class L, NL & PSPACE; Savitch's theorem; PSPACE-completeness
  • Lecture 7: NL-completeness; NL = co-NL
  • Lecture 8: Polynomial Hierarchy
  • Lecture 9: Boolean circuits; Karp-Lipton theorem; class AC and NC
  • Lecture 10: Parity not in AC^0
  • Lecture 11: Probabilistic TMs; Classes BPP, RP and ZPP; Sipser-Gács-Lautemann theorem
  • Lecture 12: Perfect matching is in RNC; Class BPL; GNI is in BP.NP
  • Lecture 13: Intro to counting complexity: class #P, #P-completeness
  • Lecture 14-15: 0/1-Permanent in #P-complete
  • Lecture 16: Class PP and ⊕P; Toda's theorem (proof sketch); Valiant-Vazirani theorem
  • Lecture 17: Proof of Toda's theorem: Randomized reduction from PH to ⊕SAT
  • Lecture 18: Proof of Toda's theorem (contd.): Deterministic reduction from PH to #SAT


• Student presentations :
  • Parity not in ACC^0[q]
  • Monotone circuit lower bound
  • Improved bounds for the Sunflower lemma
  • Formula lower bounds
  • IP = PSPACE
  • Determinant is in NC
  • An RNC algorithm for Perfect Matching