Monday, December 28, 2009

2009 Complexity Year in Review

We go all the way back to January for the paper of the year, Mark Braverman's Poly-logarithmic independence fools AC0 circuits. Runners up include the Moser-Tardos Constructive Proof of the Lovász Local Lemma (mostly for Robin Moser's great STOC talk) and Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous for QIP=PSPACE. Yet another great year for complexity.

We welcomed new bloggers Glencora BorradaileJon KatzHarry LewisRichard Lipton, and Noam Nisan. And we have a new president who promises to restore science to its rightful place.

US Science funding in general and CS funding at the NSF in particular got a strong boost from the stimulus package and continues to be well funded in the new budget. Microsoft Research New England gobbles up Madhu Sudan and Boaz Barak. A new innovations conference starts next week and we explored barriers in August. Lots of postdoc jobs out there for theorists. If you are looking for a faculty job, well you might want to consider another postdoc. 

This year we started vidcasts and typecasts with special guests Molly Fortnow, Meena Mahajan, John Rogers, Rahul Santhanam, Chris Umans and Ryan Williams.

I had a fun year. My journal ACM Transactions on Computation Theory had its first two issues (submit your papers). I discovered Twitter. I became Theory Czar (SIGACT chair) with fellow blogger Michael Mitzenmacher as vice-chair. It's hard to complain about the powers-that-be when you are a power-that-is. I had two CACM articles Time for Computer Science to Grow Up and The Status of the P versus NP Problem, another year and the problem is still open. I just started a 3-month blog sabbatical to turn the latter CACM article into a book for the masses, though I can't resist the Year in Review post. Thanks to Bill for keeping the blog going.

We remember Rajeev MotwaniAmir PnueliJack SchwartzImre Simon and Ray Solomonoff.

Thanks to our guest posters and contributors: Michele Budinich, Hans Courant, Dave Doty, Sorelle Friedler, Samir Khuller, Clyde Kruskal, Joe Kruskal, Bill Kahn, Michael Lucas, Lucy Moser, Ryan O'Donnell, Tal Rabin, Rahul Santhanam, Janos Simon, Aaron Sterling, Vijay Vazirani and Lenore Zuck.

Have a great New Years. Bill will be back next week and I'll be posting regularly again in March starting in Columbus


  1. Please let the express my thanks for this fine blog.

    Apropro of very little (except general fondness for complexity theory), the Wilmott Forum -- which is a pretty good place to hang out and learn about stochastic processes -- has a terrific article by Aaron Brown on The Necktie Paradox. You gotta love an article that features:

    Q: Could the entire universe subsist on making currency bets and trading options, with no one ever having to work again?

    A: Maybe. It depends on the volatilities.

  2. a post is better than no post. Can Bill please post something ? It's so empty without an update at all.

    Happy New Year!

  3. Mark Braverman, I'm happy for you and I'mma let you finish, but Raghavendra and Steurer's papers on SDP integrality gaps are some of the best complexity papers of all time. OF ALL TIME!

  4. A healthy and funny New Year, Bill and Lance! Keep us on "hot spots" in 2010 too! I cannot thank enough for the time you spend for us. Thanks!