In 2004, I repeated the exercise in my then young blog for the years 1995-2004. In 2005, I went back in time and chose my favorite theorems from the first decade of complexity (1965-1974) and in 2006 I covered 1975-1984, completing the backlog of the entire history of computational complexity.

Now in 2014 we start again, recapping my favorite theorems from 2005-2014, one a month from February through November with a recap in December. These theorems are chosen by a committee of one, a reward only worth the paper they are not written on. I choose theorems not primarily for technical depth, but because they change the way we think about complexity. I purposely choose theorems with breadth in mind, using each theorem to talk about the progress of a certain area in complexity. I hope you'll be presently surprised by progress we've made in complexity over the past decade.

How many people, so many opinions. So why *one* opinion (that of Lance) is so advertized? B.t.w. pointing to an Elsevier paper, closed for normal researchers, is not a real "advertisement" -- most of us cannot read them. A hint: just put a draft acceptable. Albeit your choice almost equals with mine. Am happy we have people estimating results "from the heaven".

ReplyDeleteBut please: do not ignore the "garbage work". Done by many people before.

Click the "PDF" link above to get the paper if you don't have Elsevier access.

DeleteOh, Lance, I am really sorry for me having not observed this *separate* link.

DeleteAre there any theorems that didn't make it to your lists at the time that you would

ReplyDeletewant to retroactively promote? (Demoting isn't nice, so I won't ask you to do that.)

a really great public service & a great way to see what the "insiders" think of the field. however, waiting a whole year for the list will be quite excruciating. is it because you're doing selections all year long, or do you already have the list & just want to do the writeups month by month? anyway if you could post the complete list all at once, sooner the better, that would be awesome =)

ReplyDeleteps hi SJ =)

ReplyDeleteThese theorems are chosen by a committee of one, a reward only worth the paper they are not written on.That's actually quite a lot of paper…