Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Year in Review

Expand Messages
  • Lance
    Paper of the year goes to Irit Dinur s PCP Theorem by Gap Amplification . We will never teach the PCP theorem the same way again. Concept of the year goes to
    Message 1 of 1 , Dec 29, 2005
      Paper of the year goes to Irit Dinur's PCP Theorem by Gap Amplification. We will never teach the PCP theorem the same way again. Concept of the year goes to the Unique Games Conjecture, with its applications to hardness of approximation and metric embeddings. We've also seen the settling of the complexity of Nash Equilibrium in matrix games, list decoding better than we had hoped for and much more.

      This was the year that Theory Matters and we welcomed several new bloggers in our community including Scott Aaronson and D. Sivakumar.

      A good year for math in the media. The year started with a series about a crime-solving mathematician and ended with a game show about probability, with both shows continuing into 2006. Walk into any bookstore and you'll see a number of popular books on mathematics like Mario Livio's The Equation That Couldn't be Solved and Stephen Hawking's God Created the Integers. Perhaps the biggest disappointment came from the movie Proof which never had enough traction to get a wide release in the US.

      Did I mention the White Sox won the world series?

      Thanks to guest bloggers Rahul Santhanam and Ryan O'Donnell, guest posters Boaz Barak, Ron Fagin, Bill Gasarch, Michael Mitzenmacher, Rocco Servedio, Rakesh Vohra and my first two podcast guests Bill Gasarch and Scott Aaronson. Thanks to all of your for your comments, emails, support and just reading my rambling thoughts.

      In Our Memory: George Dantzig, Seymour Ginsburg, Frank Harary, Leonid Khachiyan and Clemens Lautemann.

      Have a great New Year's. More fun in 2006.

      Posted by Lance to Computational Complexity at 12/29/2005 06:52:00 AM

    Your message has been successfully submitted and would be delivered to recipients shortly.