Computational Complexity

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.

• 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)

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?

11:11 AM #

1.  Anonymous says:  
   
   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?
   

   2:50 PM, December 11, 2006

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

   4:25 PM, December 11, 2006

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

   5:46 PM, December 11, 2006

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

   8:32 PM, December 11, 2006

5.  Anonymous says:  
   
   The first poster's count is way off: reductions ARE algorithmic results.
   
   Yeah, right and freedom fries are haute french cuisine.
   

   9:14 PM, December 11, 2006