- 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 :
- 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 : 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 :
- 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