A Short History of Computational Complexity (2002) [pdf]

Complexity classes of problems (P, NP, NP-Complete and NP-Hard) was a subject that I often had a hard time trying to get my head around it, trying to remember the concepts from college, so last year I decided to write about it [1] to improve my understanding and fixation of the subject. It turns out that while talking to other devs it seems to be a common feeling, so if you're interested in an introductory text on computational complexity I provide the link below.

[1] https://thomasvilhena.com/2019/08/complexity-classes-of-prob...

Post-2002 developments that come to mind that hadn't occurred at the time of writing: anything involving Fourier analysis of the boolean hypercube, like Ryan Williams' circuit lower-bounds & the Unique Games Conjecture, and work on pseudorandomness.

More broadly, I'm always fascinated how interaction of (probabilistic) functions is the underlying concept across such a broad swath of recent developments in complexity theory. Looking forward to seeing where the next paradigm shift comes from