**References**

#### Books/ Main references

- [Notes] Notes from the earlier offerings of this course.
- [MBNotes1] Lecture Notes: Computational Complexity by Markus Blaeser.
- [MBNotes2] Lecture Notes: Advanced Complexity Theory by Markus Blaeser
- [MBNotes3] 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)