Result of the Year goes to the new bounds on Matrix Multiplication by Andrew Stothers and Virginia Vassilevska Williams. It's not every year that we see progress on an important problem where we've had no progress since the 80's. Well there was last year. But not every year.
Some other notable results: Impagliazzo's relativized separation of Algorithmica and Heuristica, The Power of Simple Tabulation Hashing by Pătraşcu and Thorup and Property Testing Lower Bounds via Communication Complexity by Blais, Brody and Matulef
We celebrated Les Valiant's Turing Award. We remember Patrick Fischer, Phillipe Flajolet, Steve Jobs, John McCarthy and Dennis Ritchie.
Thanks to our guest posters Daniel Apon, Lauren Cowles, Annie and Molly Fortnow, Nadia Jones, Samir Khuller, Ryan O'Donnell, John Rogers, Jeffrey Stein, Aaron Sterling and Anonymous.
2011 will go down as a year when computer science started changing the world (again). Watson won on Jeopardy. Social networks brought down dictators and congressmen. Obama opens Robotics Center at Carnegie-Mellon. My daughter's high school had their first computer science class in a very long time and Stanford's AI course goes big time. The New York Times has sections on Computer Science's Sputnik Moment and the Future of Computing. The director of the Mathematical and Physical Sciences at the NSF declares "software is the modern language of science". Is there nothing CS no longer touches?
In 2012 we celebrate the man who started it all with a series of events celebrating the 100th anniversary of the birth of the father of computer science. I'll get it started next week talking on "Turing's Influence on Computational Complexity" during the AMS-ASL Special Session on the Life and Legacy of Alan Turing at the Joint Math Meeting in Boston.
"Result of the Year" goes to a minor improvement on the analysis of a decades-old algorithm that brought no new insights?
ReplyDeleteI for one consider the fact that \omega is lower than we thought for decades is an insight in and of itself.
ReplyDeleteSure there was no reason it *could not be* lower, but there was no indication that it *could be* until this result.
Remember that Stothers objected to being called Andy on Scott's blog and that was the only thing he objected to?
ReplyDeleteI'm with Anon@9:46. Among the papers you mentioned, I would have picked Mihai and Mikkel's tabulation hashing paper over the new matrix multiplication bounds in a heartbeat.
ReplyDeleteBut my favorite theory result of the year is this one: http://arxiv.org/abs/1105.2228
I changed "Andy" to "Andrew". Thanks.
ReplyDeleteAndrew Stothers' result is the result of *last* year.
ReplyDelete