This work is licensed under a
Creative Commons License.
|
Monday, March 15, 2004
Favorite Theorems: Derandomization
Posted by Lance
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 1997The 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(2O(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.
4:57 PM
#
Links to this post:
Weblog Home
Archives
