Computational Complexity Theory

We will try to keep the references as lecture notes since the topics and presentations are chosen from various places and shall give references accordingly. We will try to make a rough/short draft/plan available in the course website before each class. The (somewhat detailed) lecture notes which are scribed by the students will be posted when completed.

As a general reference, we will use an excellent book covering most of the new areas in complexity theory : Complexity Theory: A Modern Approach - Sanjeev Arora and Boaz Barak.

There are plenty of very good introductory books in classical complexity theory

Structural Complexity I & II - Jose Luis Balcazar, Joseph Diaz and Joaquim Gabarro.
Computational Complexity: A Conceptual Perspective, by Goldreich (free drafts).
Computational Complexity - Christos H. Papadimitriou.
Theory of Computational Complexity - Ding-Zhu Du and Ker-I Ko.
Introduction to Circuit Complexity: A Uniform Approach - Heribert Vollmer

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 on the Fusion Method and Derandomization (lectures by Avi Wigderson).
Around the PCP Theorem - Lectures by Sanjeev Arora
Introduction to Complexity Theory Two sets of Lecture Notes - Oded Goldreich
Advanced Complexity Theory - Madhu Sudan
Lecture Notes on Computational Complexity - Luca Trevisan
Lectures in Computational Complexity, by Jin Yi Cai
Dieter van Melkebeek's lecture notes.
Paul Beame's lecture notes.
Peter Bro Miltersen's lecture notes.
Kristoffer Hansen's Course.
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.