A few years ago in 2021, I put together a guide to resources for learning computational complexity theory at the graduate level [0]. Think time and space complexity, hierarchy theorems, and circuit complexity.<p>For video lectures, for instance, I recommended Ryan O’Donnell undergraduate [1] and graduate classes [2] at CMU. To keep this up to date, I want to add more options for lecture notes and videos.<p>Have you worked through a new book or a recent set of lectures that were helpful?<p>[0]: https://bcmullins.github.io/complexity_theory_resources/<p>[1]: https://www.youtube.com/playlist?list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2<p>[2]: https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH
There is the textbook "Computational Complexity: A Modern
Approach" by Arora and Barak with a freely accessible draft:<p><a href="https://theory.cs.princeton.edu/complexity/book.pdf" rel="nofollow">https://theory.cs.princeton.edu/complexity/book.pdf</a>