- Instructors : Chandan Saha Course number and Credits : E0 224 and 3:1 Lecture time : Tu,Th 11-12:30 Venue : CSA 117
- TAs : Abhishek Shetty and Sanal Prasad
- Syllabus :
- 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
- References :
- Computational Complexity - A Modern Approach by Sanjeev Arora and Boaz Barak
(We'll closely follow this book)
- Computational Complexity Theory by Steven Rudich and Avi Wigderson (Editors)
- Gems of Theoretical Computer Science by Schoening and Pruim
- The Nature of Computation by Moore and Mertens
- The Complexity Theory Companion by Hemaspaandra and Ogihara
- Online lecture notes... (take a look at this webpage)
- Prerequisites : Familiarity with undergraduate level data structures & algorithms, and mathematical maturity.
- Grading policy :
- Assignments - 30%
- Mid-term exam - 30%
- End-term exam - 40%
- Announcements:
- Abhishek and Sanal would be offering tutorials on NP-complete problems on Thursday (Aug 18) and Saturday (Aug 20). Time: 11:00-12:30 and 15:00-16:30 respectively. Venue: CSA 117
- Tutorial on Oracle Turing machines and Baker-Gill-Solovay theorem on Thursday (Sep 1). Time: 11:00-12:30. Venue: CSA 117
- Sep 6: First set of assignment problems is up! (see below)
- Mid-term exam on October 8, 2016 (Saturday). Time: 10:00-13:00. Venue: CSA 117
- Discussion of solutions to assignment 1 problems on Friday (Oct 7). Time: 18:00-19:30. Venue: CSA 252
- Csanky's algorithm will be discussed by Abhishek and Sanal on Tuesday (Oct 11). Time: 11:00-12:30. Venue: CSA 117
- Nov 11: Extra class on Nov 19 (Saturday). Time: 15:00-16:30. Venue: CSA 117
- End-term exam on December 15, 2016 (Thursday). Time: 10:00-13:00. Venue: CSA 117
- Assignments :
- Lectures :
- Lecture 1: Introduction; Turing machines; Class P
- Lecture 2: Class NP; Karp reductions; NP-completeness
- Lecture 3: Cook-Levin theorem
- Lecture 4: NTMs; Search versus decision; Class co-NP and EXP
- Tutorial 1: NP-complete problems - Quadeq, Indset, Vertex cover, Clique, Farthest string
- Tutorial 2: NP-complete problems - 3D matching , Steiner tree , Subset sum , Minesweeper (consistency and inference )
- Lecture 5: Diagonalization; Time Hierarchy; Ladner's theorem
- Lecture 6: Ladner's theorem (contd.); Space complexity
- Lecture 7: Savitch's theorem; TQBF is PSPACE-complete
- Tutorial 3: Relativization; Baker-Gill-Solovay theorem; other examples of diagonalization
- Lecture 8: Logspace reductions; PATH is NL-complete; certificate definition of NL
- Lecture 9: NL = co-NL; Polynomial Hierarchy
- Lecture 10: Polynomial Hierarchy (contd.)
- Lecture 11: Polynomial Hierarchy (contd.); Boolean circuits
- Lecture 12: Boolean circuits (contd.): Karp-Lipton theorem, classes AC and NC
- Lecture 13-14: Parity not in AC0
- Lecture 15: P-completeness; Randomized computation
- Lecture 16: Perfect matching in RNC; class BPP
- Lecture 17: Class BPP (contd.); Hadamard codes; Sipser-Gács theorem
- Tutorial 4: Csanky's algorithm: determinant computation is in NC
- Lecture 18: Discussion on mid-term exam problems; classes RP, co-RP and ZPP
- Lecture 19: BPP in P/poly; randomized reduction, class BP.NP
- Lecture 20-21: Graph nonisomorphism is in BP.NP
- Lecture 22: Counting complexity: class #P, #P-completeness
- Lecture 23-25: 0/1 Permanent is #P-complete
- Lecture 26: Class PP, ⊕P; Valiant-Vazirani theorem
- Lecture 27-28: Toda's theorem: PH in P^#SAT
- Lecture 29: PCP: Intro; equivalence of two views
- Lecture 30: Equivalence of two views (contd.); hardness of approximation of Max-Indset
- Lecture 31: NP in PCP(poly(n),1)