Computational Complexity Theory

• Instructor : Chandan Saha,   TA : Agrim Dewan,   Course number and Credits : E0 224 and 3:1,   Lecture time : M,W 11:30-1 pm,   Venue : CSA 112.


• Syllabus :
  • P, NP and NP-completeness
  • Space complexity
  • Polynomial time hierarchy
  • Boolean circuits
  • Randomized computation
  • Complexity of counting
  • Basics of hardness of approximations (if time permits)


• 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 some mathematical maturity.


• Grading policy :
  • Assignments - 45%
  • Presentation - 25%
  • Final exam - 30%


• Assignments :
  • Assignment 1 (due date: Sep 20, 2024)
  • Assignment 2 (due date: Oct 20, 2024)
  • Assignment 3 (due date: Nov 14, 2024)


• Lectures :
  • Lecture 1: Course overview; Turing machines
  • Lecture 2: Turing machines (contd.); Class P
  • Lecture 3: Class P (contd.); Class NP; Karp reductions; NP-completeness
  • Lecture 4: Cook-Levin theorem
  • Lecture 5: Cook-Levin theorem (contd.); More NP-complete problems
  • Lecture 6: More NP-complete problems; Search versus Decision
  • Lecture 7: NTMs; Class co-NP
  • Lecture 8: Class EXP; Time Hierarchy theorem; Ladner's theorem
  • Lecture 9: Ladner's theorem (contd.); Relativization
  • Lecture 10: Space complexity classes; Savitch's theorem
  • Lecture 11: PSPACE-completeness; Log-space reductions
  • Lecture 12: NL-completeness; NL = co-NL
  • Lecture 13: Polynomial Hierarchy
  • Lecture 14: Polynomial hierarchy (contd.); Boolean circuits: class P/poly; Karp-Lipton theorem
  • Lecture 15: Class NC and AC; P-completeness
  • Lecture 16: Parity not in AC^0
  • Lecture 17: Switching lemma; PTMs; Class BPP
  • Lecture 18: Class BPP (contd.); Sipser-Gacs-Lautemann theorem; Classes RP and ZPP
  • Lecture 19: Perfect matching is in RNC; Class BPL; Randomized reductions
  • Lecture 20: GNI is in BP.NP
  • Lecture 21: Complexity of Counting; 0/1 Permanent is #P-complete
  • Lecture 22: Class PP and ⊕P; Valiant-Vazirani theorem
  • Lecture 23: Toda's theorem: Randomized reduction from PH to ⊕SAT
  • Lecture 24: Toda's theorem: Deterministic reduction from PH to #SAT
  • Lecture 25: Natural proofs (by Agrim)