Saturday, June 20, 2009

Gowers on Razborov's theorem about monotone circuit complexity

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.

No comments: