Ask HN: New Resources for Learning Complexity Theory

13 points

2 years ago

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.

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.

Have you worked through a new book or a recent set of lectures that were helpful?

[0]: https://bcmullins.github.io/complexity_theory_resources/

[1]: https://www.youtube.com/playlist?list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2

[2]: https://www.youtube.com/playlist?list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH

1 comment