The joyous lion of theoretical computer science(Read here a story about Avi and me related to the above picture.)

Boaz Barak is reporting on Avi Wigderson’s book Mathematics and Computation which is on Avi’s homepage. I read through an earlier version and it is highly recommended! Let me also recommend Avi’s earlier survey on interaction between CS and math.

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…

View original post 140 more words