Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] Favorite Theorems: Derandomization

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 2 , Mar 15, 2004
    • 0 Attachment
      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(2O(n)) such that there exists an ε>0 such that for all n, there are no circuits of size 2εn that computer 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.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 3/15/2004 04:57:20 PM

    • Lance Fortnow
      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
      Message 2 of 2 , Mar 15, 2004
      • 0 Attachment
        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(2O(n)) such that there exists an ε>0 such that for all n, there are no circuits of size 2εn that computer 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.

        --
        Posted by Lance Fortnow to My Computational Complexity Web Log at 3/15/2004 04:57:20 PM

      Your message has been successfully submitted and would be delivered to recipients shortly.