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

Sanjeev Arora and Boaz Barak
Computational Complexity: A Modern Approach
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: …

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.