2008 Complexity Year in Review

Paper of the year goes to Optimal algorithms and inapproximability results for every CSP? by U. Washington grad student Prasad Raghavendra. The paper gives a semidefinite program approximating any constraint satisfaction problem, always the best possible approximation if the unique games conjecture holds.

Some other notables: Aaronson-Wigderson's Algebrization, Raz's counterexample to the strong parallel repetition theorem and many others. Another good year for Complexity.

Despite the dozens of "proofs" that have come my way, the P vs. NP problem remains open. Maybe next year.

NSF funding for theoretical computer science are at the highest levels since I started this blog. Princeton hosts a new NSF sponsored Center for Computational Intractability and Microsoft opened a new research lab in Cambridge, Mass. The theoretical computer science landscape looks quite strong.

However the current economic crisis will pose great challenges to computer science and all of academics as university budgets tighten. Great research can happen in awful economies—computability theory got its start during the great depression for example. But we all suffer if we lose a generation of theorists to this economy.

We remember David Gale, Nick Reingold, Ingo Wegener and others who inspired our lives, George Carlin, Arthur C. Clarke, Michael Crichton, Bobby Fischer and Randy Pausch.

We thank guest posters Richard Beigel, Manuel Bodirsky, Rance Cleavland, Iftah Gamzu, Evan Golub, Nicole Immorlica, Kamal Jain, Joe Kruskal, James Lee, Richard Matthew McCutchen, Amir Michail, Ketan Mulmuley, Vahan Mkrtchyan, Kirk Pruhs, Ken Regan, Rahul Santhanam, Uzi Vishkin, Philipp Woelfel and Jens Zumbraegel for their contributions to our blog this year.

A personal thanks to Bill Gasarch, not only for allowing me to come back to the blog and staying on as co-blogger, but also for organizing a great Computational Complexity Conference at Maryland.

I will always have many great memories for 2008. I started a new job at Northwestern in January and it was a great first year. My eldest daughter became a teenager and had her Bat Mitzvah in May. And after an entertaining election season, our junior senator is just weeks away from becoming the first African-American president of these United States of America. An exciting year indeed.