Main Text Book:
- [AB Book] : Complexity Theory: A Modern Approach - Sanjeev Arora and Boaz Barak. (Availability : There are 2 copies each in the IITM and CSED libraries).
Reference Text Books:
- [G Book] : Computational Complexity: A Conceptual Perspective, by Goldreich (free drafts). (Availability : There is 1 copy at the department library).
Lecture Notes:You can refer to the previous version of this course here. The lecture notes are also uploaded.
There are plenty of excellent lecture notes for similar courses that are available on the internet. Following are some of them which has materials relevant to this course too. Specific references will be provided whenever necessary.
- Complexity Theory Lecture Notes - Eric Allender
- Lectures in Computational Complexity, by Jin Yi Cai
- Lecture Notes on Computational Complexity - Luca Trevisan
- Kristoffer Hansen's Course.
- Advanced Complexity Theory - Madhu Sudan
- Introduction to Complexity Theory Two sets of Lecture Notes - Oded Goldreich.
- Dieter van Melkebeek's lecture notes.
- Paul Beame's lecture notes.
- Peter Bro Miltersen's lecture notes.
- Chris Umans's lecture notes.
- Johan Hastad's lecture notes.
- Andrej Bogdanov's lecture notes.
- Dan Spielman's lecture notes.
- Moni Naor's lecture notes.
- Jaikumar Radhakrishnan's lecture notes.
- Steven Rudich's lecture notes.