This work is licensed under a
Creative Commons License.
|
Monday, December 11, 2006
Favorite Theorems: Second Decade Recap
Posted by Lance
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.
- Alternation (Chandra-Kozen-Stockmeyer)
- Relativization (Baker-Gill-Solovay)
- Small Sets (Mahaney)
- Primality Algorithms (Solovay-Strassen, Miller, Rabin)
- Probabilistic Complexity (Gill, Sipser)
- The Permanent (Valiant)
- Unique Witnesses (Valiant-Vazirani)
- Parity (Furst-Saxe-Sipser, Ajtai)
- The Yao Principle (Yao)
- Nonuniform Complexity (Karp-Lipton)
Next favorite theorems in 2014. Will your name be on that list?
11:11 AM
# 5 comments
-
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?
-
Kind of inline with the first poster; I would like to see your favorite algorithms list.
-
The first poster's count is way off: reductions ARE algorithmic results.
-
Funny: Shor's quantum factoring algorithm did not make it to any of the lists.
-
The first poster's count is way off: reductions ARE algorithmic results.
Yeah, right and freedom fries are haute french cuisine.
Links to this post:
Weblog Home
Archives
