What were the most surprising results in complexity?
I think it would be useful to have a list of unexpected/surprising results. This includes both results that were surprising and came out of nowhere and also results that turned out different than people expected.
Edit: given the list by Gasarch, Lewis, and Ladner on the complexity blog (pointed out by @Zeyu), let's focus this community wiki on results not on their list. Perhaps this will lead to a focus on results after 2005 (as per @Jukka's suggestion).
An example: Weak Learning = Strong Learning [Schapire 1990]: (Surprisingly?) Having any edge over random guessing gets you PAC learning. Lead to the AdaBoost algorithm.