Avi Wigderson is one of the most prolific and creative theoretical computer scientists (in fact, he is one of the most prolific and creative scientists, period). Over the last several years, Avi had worked hard into distilling his vast knowledge of theoretical computer science and neighboring fields into a book surveying TCS, and in particular computational complexity, and its connections with mathematics and other areas.
I’m happy to announce that he’s just put a draft of this upcoming book on his webpage.
The book contains a high level overview of TCS, starting with the basics of complexity theory, and moving to areas such as circuit complexity, proof complexity, distributed computing, online algorithms, learning, and many more. Along the way there are interludes about the connections of TCS to many mathematical areas.
The book is highly recommended for anyone, but in particular for undergraduate and beginning graduate students that are interested in complexity and related areas.
Every TCS researcher should read Chapter 20 (“epilogue”) of the book. That chapter can be read on its own, and gives a bird-eye’s view of TCS and many of its past achievements, interactions with other sciences, and future directions. As anyone who knows Avi can attest, no one quite has as much a deep understanding of so many topics, and getting Avi’s point of view on any issue is always a treat. For example, the section on the firewall paradox for black holes gives an accessible taste of a fascinating (and highly technical) area where computational complexity intersects with some of the most basic questions in theoretical physics.
To sum up, just read the book. I also plan to recommend it to my students, and use parts of it as ways to enrich my courses.