Favorite Theorems: Derandomization

As I had mentioned earlier, this year I plan to write My Favorite Ten Complexity Theorems of the Past Decade II. I decided to reveal the choices one per month through the end of 2004.

For March I will go with derandomization, an area where we have seen amazing progress in recent years. My favorite derandomization result in the past decade is

P=BPP unless E has subexponential circuits: Derandomizing the XOR Lemma
by Russell Impagliazzo and Avi Wigderson, STOC 1997

The title both describes the main result and the technique use to prove it. Informally this result says that under a believable hardness assumption one can get full derandomization. Formally, if there exists a language L computable in DTIME(2^O(n)) such that there exists an ε>0 such that for all n, there are no circuits of size 2^εn that compute L on inputs on length n then pseudorandom generators exist and P=BPP.

This paper marks the culmination of a series of papers to derandomize BPP. We have also seen many papers since giving connections between derandomization and other recent areas in complexity like extractors and error-correcting codes as well as other applications for derandomization. I can't mention all of these results in this post but I recommend the survey of Valentine Kabanets and the book chapter of Peter Bro Miltersen for a broader background on derandomization.