Thursday, January 16, 2014

Favorite Theorems: Introduction

I was invited to give a talk at the FST&TCS conference held in December 1994 in Madras (now Chennai). As I searched for a topic, I realized I was just finishing up my first decade as a computational complexity theorist so I decided to recap the past decade by listing My favorite ten complexity theorems of the past decade (PDF). Not so much to choose winners, but use the theorems to survey the great research during those past ten years.

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.


  1. 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".

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

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

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

  2. Are there any theorems that didn't make it to your lists at the time that you would
    want to retroactively promote? (Demoting isn't nice, so I won't ask you to do that.)

  3. 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 =)
    ps hi SJ =)

  4. These 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…