We had quite an active year in complexity and Paper of the Year goes to Martin Fürer's Faster Integer Multiplication, making a breakthrough in this most basic of algorithmic questions.
This blog, now under new leadership, hit five years and 1000 posts in August. Most commented post: Vijay Vazirani's post suggesting that submissions to conferences come with an accompaning video followed closely by Claire Kenyon's post on cover letters.
Back in February I posted about large proposed increases in the NSF budget but with a caveat that it had to survive the congressional appropriation process. It didn't.
In 2007 we mourned theorists Steve Mahaney and Andrej Muchnik as well as others close to our heart: Martin Kruskal, Jim Gray, John Backus and Paul Cohen.
Bill and I would like to thank our guest posters Kamal Jain, Jonathan Katz, Claire Kenyon, Shiva Kintali, Phil Klein, Stuart Kurtz, Clyde Kruskal, Nicole Immorlica, Amir Michail, Mihai Patrascu, Ken Regan, Jim Royer, Alexander Shen and Vijay Vazirani. Most of all thanks to Bill for keeping this blog active and still going strong.
Here's wishing everyone a great 2008!
Happy new Year! ^_^
ReplyDeletehappy new year~
ReplyDeleteHappy new year indeed! In an article a few links away you mentioned that for any k, the graph minor theorem implies the existence of an O(n**3) algorithm for determining whether a graph G has genus k. Do you happen to know if the converse is either 1) known to be true; or if not, then 2) has any hope of being true? That is, does the O(n**3) existence statement imply the graph minor theorem?
ReplyDeleteThe idea of a nonconstrutive proof of existence of an O(n**3) algorithm is interesting. Has there been anything like that before?
Thanks.