Hacker News Reader

The next step book wise is Arora and Barak, Computational Complexity: a modern approach. Of course that book is already out of date. The breakthrough that comes to mind is Ryan Williams' circuit lower bounds. He wrote a nice explanation of the proof here: https://arxiv.org/abs/1111.1261 He defines all the key terms pretty well but probably requires a bit of "maturity" to understand. There are also various breakthroughs to do with interactive proofs.

View on HN

Not OP but while I aced my class that used Sipser's book, nevertheless I still lacked the mathematical comfort/maturity to do Arora and Barak. The first class started talking about "random functions" and I had no background for that at the time. I don't know if some kind of advanced discrete math class would have helped fill in the gaps at the time, at least for myself. Or maybe a remedial discrete math class, I was mainly an engineer not originally intending to be a CS major.

There is the textbook by Papadimitriou, I don't have a copy but I once taught a class that had been based on that book and slightly updated to include elements from Arora Barak. I think it's still a jump up from Sipser but perhaps a little gentler than AB. Ymmv

Reply on news.ycombinator.com