Monday, December 11, 2006

Favorite Theorems: Second Decade Recap

This past year I listed my favorite computational complexity theorems from 1975-1984. I have now completed my favorite theorems cycle for the first four decades of complexity including 1965-74, 1985-94 and 1995-2004.

Next favorite theorems in 2014. Will your name be on that list?

5 comments:

  1. It is interesting to see that the last decade (1994-2004) contains more algorithmic results (derandomization, primes, decoding) than the other three decades combined. Is this a coincidence or does it reflect a change how the field approaches the age old questions from CC?

    ReplyDelete
  2. Kind of inline with the first poster; I would like to see your favorite algorithms list.

    ReplyDelete
  3. The first poster's count is way off: reductions ARE algorithmic results.

    ReplyDelete
  4. Funny: Shor's quantum factoring algorithm did not make it to any of the lists.

    ReplyDelete
  5. The first poster's count is way off: reductions ARE algorithmic results.

    Yeah, right and freedom fries are haute french cuisine.

    ReplyDelete