Text Books:
As a general references for the course we will use the following books:- Complexity Theory: A
Modern Approach - Sanjeev Arora and Boaz Barak.
(Availability : There is 1 copy each in the IITM and CSED libraries). - Computational
Complexity: A Conceptual Perspective, by Goldreich (free drafts).
(Availability : We have ordered 1 copy for the department library).
There are plenty of very good introductory books in classical complexity theory
- 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
- Structural Complexity I & II - Jose Luis Balcazar, Joseph Diaz and Joaquim Gabarro.
Lecture Notes:
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.
- Lectures on the Fusion Method and Derandomization (lectures by Avi Wigderson).
- Around the PCP Theorem - Lectures by Sanjeev Arora
Last updated on Fri May 13 21:08:49 IST 2011