I mentioned before that I’d been to Tim Gowers’s lectures on computational complexity. As I noted before, videos of his lectures are available here. But, as promised, he has also written up the proof which was the topic of the first part of the course, namely Razborov’s demonstration that the monotone circuit complexity of the clique function is superpolynomial. You can read it here. Tim Gowers puts a lot of effort into making the ideas seem reasonably “natural”. Enjoy! — if you have a taste for this sort of thing.
- Now 125+ Logical Snippets at https://t.co/8BzsQyJzhO Answers to qns of interest to beginning/intermediate logic students. Spread the word!, 1 hour ago
- RT @I__Love__Italy: Venice https://t.co/EIGQrKe0JD, Nov 20
- Was fine exhib at Nat Gal of C19 purchases, incl “Botticelli” that’s now OBV not! Bet this’ll be in 2117 exhib of… https://t.co/RAqeFr6Xsx, Nov 16
- RT @JohnRentoul: @georgeeaton Let’s build on it & create an island megalopolis! https://t.co/vc4bjQGR3c, Nov 16
- RT @venezia_56: Dogana da Mar #Benoni Punta della Salute Sull' orizzonte la Giudecca e la Chiesa e Ospizio delle Zitelle… https://t.co/QVvYr6qAOK, Nov 16