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.