[Computational Complexity] Year in Review
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.
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.
Have a great New Year's. More fun in 2006.
Posted by Lance to Computational Complexity at 12/29/2005 06:52:00 AM