Favorite Theorem: PCP Simplified

The famous Probabilistically Checkable Proof Theorem due to Arora, Lund, Motwani, Sudan and Szegedy states that every problem in NP has a proof that can be checked efficiently by a verifier using O(log n) random coins and a constant number of queries. Not only amazing in its own right, the PCP theorem has significant implications for hardness of approximation. In its strongest form, no efficient algorithm can maximize the number of satisfying clauses in a formula better than a 7/8 approximation unless P = NP. Both of these results have been on my previous favorite theorems lists so lets add one more.

The PCP Theorem by Gap Amplification by Irit Dinur (PDF)

Dinur's main result doesn't prove a new theorem per se but gives a much simplified and intuitively understandable proof than the original paper. She increases the approximation gap by using an expansion graph though this causes an increase in the alphabet size which she reduces using another transformation. Repeating these steps yields the theorem. Unless you need tight bounds, Dinur's proof is the one to teach or read. 

Dinur's paper followed shortly after Omer Reingold's theorem on undirected connectivity, and while these are very different proofs of different results, together they show the amazing power of expander graphs in computational complexity.