This work is licensed under a
Creative Commons License.
|
Thursday, December 29, 2005
Year in Review
Posted by 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 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
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.
6:52 AM #
-
Why do we call the original
PCP proof nonelementary
and the new proof elementary?
If I understand correctly, non elementary means
involving complexity analysis, like the first
proof of prime number theorem. Elementary does not use complex analysis,
like Erdos-Selberg proof
of PNT. If this is true,
then both proofs of
PCP are elementary, right?
-
And the award for "TCS Blogger of the year" goes to you Lance. Thanks.
The readers.
-
True, mathematicians distinguish proofs on the basis you describe, which makes almost all of computer science 'elementary'. Obviously this is not a useful criterion for practitioners of complexity, nor do they use it this way.
The most obvious use of the term 'elementary proof' is to mean 'short proof', or, more strictly and recursively, 'short proof that doesn't have to invoke any results that don't yet have elementary proofs'.
I think the term also indicates that the techniques used in the proof are relatively familiar to most researchers. Thus, the most elementary proofs are those that are based on simulation techniques (and relativize). Somewhat less so are probabilistic arguments, then comes algebraic techniques.. if you've proved something that crucially uses topology or complex analysis towards answering questions basic to computational complexity (as opposed to showing NP-completeness of a topological problem, say), give yourself a cookie--that's probably a non-elementary proof.
-
What is your (and readers') take on the most surprising result of the year? That is, the most surprising theorem (proofs aside)?
-
I second the suggestion that Lance be given the TCS blogger of the year title.
Thanks
Amar
-
I will offer a vote for the ppad-hardness of 2-player nash being surprising. for siva's sake, let me clarify "surprising":
It is a long-standing open problem that a significant fraction of people thought would be resolved with an algorithm finding equilibria in such games.
-
Lance, many thanks for the so many pleasant hours i spent in front of your blog. Let me make a wish for 2006: I think our community deserves its own forum. Maybe you can add such a forum to your blog?
Links to this post:
Weblog Home
Archives
