- Instructors : Chandan Saha Course number and Credits : E0 224 and 3:1 Lecture time : M,W 3:30-5 pm Venue : CSA 117
- 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 - 20%
- Presentation - 10%
- Scribing - 10%
- Mid-term exam - 30%
- End-term exam - 30%
- Assignments :
- Lectures :