CS60069 - Computational Complexity Theory

Brief Syllabus:

Elementary space and time complexity classes, inclusion theorems, randomization, circuit complexity classes, counting classes, sublinear space, interactive proof systems.

Course books:

Computational Complexity, by Christos H. Papadimitriou, Addison-Wesley publishers.

Introduction to the Theory of Computation, by Michael Sipser.

Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak.