Thursday, December 28, 2006

2006 Year in Review

The paper of the year goes to Settling the Complexity of 2-Player Nash-Equilibrium by Xi Chen and Xiaotie Deng which finished characterizing the complexity of one of the few problems between P and NP-complete. The paper won best paper award at FOCS.

The story of the year goes to Grigori Perelman, his proof of the Poincaré Conjecture, his declining of the Fields Medal and Shing-Tung Yau's portrayal in the New Yorker and the lawsuit threat that followed. Science magazine named Perelman's proof the Breakthrough of the Year.

Meanwhile the theory-friendly number theorist Terrence Tao accepted his Fields medal and CMU cryptographer Luis von Ahn and Tao won MacArthur genius awards.

My post FOCS Accepts and a Movie received over 200 comments mostly about the state of the theory conferences. Sadly the movie and the rest of the site have disappeared. I also finished my favorite complexity theorems, at least for now.

In 2006 we celebrated the centennials of the births of Kurt Gödel and Richard Rado and mourned the early death of Mikhail Alekhnovich.

Thanks to guest blogger Claire Kenyon, guest posters Eldar Fischer, Jérémy Barbay, Janos Simon and podcast guests Luis Antunes, Eldar Fischer, Troy Lee and his opponents. The biggest thanks to Bill Gasarch who did all of the above several times.

Happy New Years to all my readers and let's look forward to an exciting FCRC and a renewed US commitment to increased funding in the basic sciences.


  1. Terry Tao spans many areas but I don't think he is classified as a number theorist - his primary area seems to be analysis.

  2. Terry Tao spans many areas but I don't think he is classified as a number theorist - his primary area seems to be analysis.

    Given that probably his most prominent theorem is arbitrarily long arithmetic sequences in the primes, I think it's perfectly reasonable to call him a number theorist. Unless you're one of those people that only thinks algebraic number theory is number theory, and analytic number theory doesn't count.

  3. While we are assigning people their arbitrary classifications, is Luis really a cryptographer?

  4. He can be classified to work both in crypto, AI, and their intersecation. Some of his work - like stegonography - is more related to crypto, some - like using games to label images - is more related to AI, and some - like CAPTCHAS - is really on the intersection of crypto and AI.

    Alternatively, perhaps we should play one of Luis' games to label him properly :).

  5. Sure, Terry has written an important paper with number-theoretic conclusions, but it's very misleading to call him a number theorist (and I don't believe he would call himself one). He's an analyst. Virtually all of his papers are not in number theory, and he doesn't have a lot of background in number theory or follow much of the number theory literature. He's probably more a number theorist than Manindra Agrawal is (to pick another prominent example of a non-number theorist who has proved a great theorem in number theory), but not overwhelmingly.

    The second commenter seems to think this opinion is a form of snobbery, but I don't intend it that way. Terry's a brilliant mathematician who can do whatever sort of research he wants, but his background and primary interests are not in number theory.

    (By the way, I don't know of anybody who thinks only algebraic number theory counts as number theory.)