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
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.
Why do we call the original
ReplyDeletePCP 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.
ReplyDeleteThe 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.
ReplyDeleteThe 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)?
ReplyDeleteI second the suggestion that Lance be given the TCS blogger of the year title.
ReplyDeleteThanks
Amar
I will offer a vote for the ppad-hardness of 2-player nash being surprising. for siva's sake, let me clarify "surprising":
ReplyDeleteIt 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?
ReplyDelete