References

Books/ Main references

• [Notes] Notes from the earlier offerings of this course.
• [MB Notes1] Lecture Notes: Computational Complexity by Markus Blaeser.
• [MB Notes2] Lecture Notes: Advanced Complexity Theory by Markus Blaeser
• [MB Notes3] Lower bounds and derandomization: Lecture notes by Markus Blaeser
• [AB] Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak.
• [Gold] Computational Complexity: A Conceptual Perspective , by Goldreich.
• [K Book] : Theory of Computation - Dexter Kozen
  
• [Vollmer] Heribert Vollmer: Introduction to Circuit Complexity (A Uniform Approach), Springer-Verlag 1999
• [Jukna] Stasys Jukna : Boolean Function Complexity: Advances and Frontiers Springer-Verlag 2011

Lecture Notes:

There are many lecture notes available on the internet with contents similar to this course. The following is a non-exhaustive list. 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 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).
• Lecture notes on interactive proofs by Jaikumar Radhakrishnan. (Has a detailed account on PCP theorem, and the first proof.)
• Lecture notes by V Vinay (Contains good material on Circuit Complexity)