Computational Complexity

Abstract

Thanks to Luca Trevisan for starting this column about theoretical computer science blogs and for asking me to write one of the first columns. Luca said he was interested in knowing what inspired me to start my blog, how I thought about topics (that is, the balance between technical and non-technical content and at what level to address the technical content), why I chose the green background
and so on. He also suggested I update a favorite post.
This column thus expands and updates two June 2009 blog posts, The Story of the Blog [3] and A Kolmogorov Complexity Proof of the Lovász Local Lemma [2], the latter about the most mind-blowing STOC talk I ever attended.