Favorite Theorems Preview

I have written up my ten favorite theorems for the decades 1985-1994, 1995-2004 and 1965-1974. This year we tackle the remaining decade 1975-1984, the second major decade in complexity and the decade leading up to when I started graduate school in 1985.

The first decade set the groundwork for computational complexity and the P versus NP problem. In the second decade attempts to understand and solve the P versus NP problem led to new and interesting questions that still challenge us today. But we most remember the second decade for analyzing different models of computation such as alternation, parallel, probabilistic, circuits, interactive proofs and the first hints of quantum computers.

Starting next month I will run down my favorite theorems of the decade that showed that the tools of computational complexity can help us understand efficient computation in whatever form it comes in.