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. (Sept 19) here is a post devoted to two major messages from the book.

Update (Sept, 19): The book is now published.Congratulations.

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

Pingback: Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations | Combinatorics and more

Pingback: Itai Benjamini and Jeremie Brieussel: Noise Sensitivity Meets Group Theory | Combinatorics and more

Pingback: Avi Wigderson’s: “Integrating computational modeling, algorithms, and complexity into theories of nature, marks a new scientific revolution!” (An invitation for a discussion.) | Combinatorics and more

Pingback: Quantum computers: amazing progress (Google & IBM), and extraordinary but probably false supremacy claims (Google). | Combinatorics and more