Ask HN: New Resources for Learning Complexity Theory
13 points
23 days ago
| 1 comment
| HN
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

▲
Tryk
23 days ago
[-]
There is the textbook "Computational Complexity: A Modern Approach" by Arora and Barak with a freely accessible draft:

https://theory.cs.princeton.edu/complexity/book.pdf

reply