A Personal View of Average-Case Complexity (1995) [pdf]

gwern.net

63 pointsftxbro3 comments

Super unrelated, somehow this post crashes the Harmonic HN news app on Android when scrolling through the feed.

This is my favorite complexity paper. It reminds us of how much we don’t know.

Do you have any other interesting complexity theory ones to recommend?