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.

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

ReplyDeleteresultof the year? That is, the most surprising theorem (proofs aside)?I second the suggestion that Lance be given the

ReplyDeleteTCS blogger of the yeartitle.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":

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