- Instructors : Chandan Saha Course number and Credits : E0 224 and 3:1 Lecture time : Tu,Th 3:30-5 pm Venue : CSA 252
- TAs : Nikhil Gupta and Vineet Nair
- 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 - 30%
- Presentation - 10%
- Announcements:
- No class on Aug 15.
- Mid-term exam on October 7, 2016 (Saturday). Time: 10:00-13:00. Venue: CSA 252
- Assignments :
- Lectures :