- Instructors : Chandan Saha Course number and Credits : E0 224 and 3:1 Lecture time : M,W 11:00-12:30 Venue : CSA 117
- TA : Palash Dey
- Objective : Computational complexity theory is the fundamental subject of classifying computational problems based on their `complexities'. In this context, `complexity' of a problem is a measure of the amount of resources (time/space/random bits/queries etc.) used by the best possible algorithm that solves the problem. The aim of this course is to give a basic introduction to this field. Starting with the basic definitions and properties, we intend to cover some of the classical results and proof techniques of complexity theory.
- Syllabus (tentative):
- Turing machines - a computational model
- P, NP and NP-completeness
- Diagonalization and Relativization
- Space complexity
- Polynomial time hierarchy
- Boolean circuits
- Randomized computation
- Interactive proofs
- 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 : 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 September 29, 2014 (Monday). Time: 11:00-13:00. Venue: CSA 117
- Neeldhara Misra has offered a couple of lectures (14 & 15) on Boolean circuits. Please find the slides and lecture note prepared by her below.
- End-term exam on December 10, 2014 (Wednesday). Time: 10:00-13:00. Venue: CSA 117
- Assignments :
- Lectures (unedited notes scribed by students):