More books that I don’t have time to read:

Sanjeev Arora and Boaz Barak
Computational Complexity: A Modern Approach
2007
pdf link

via this tweet by Susan Holmes:

I think one of the big breakthroughs from a practical viewpoint was the insight that there are differing degrees of complexity in NP, see the online book here:http://theory.cs.princeton.edu/complexity/book.pdf …

Looking at the ToC of that book: Woah. I knew that I don’t know much about complexity theory, but I thought I knew at least basic introductory theory. Now I realize I’ve only scratched the surface.