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

[Computational Complexity] Uniform Derandomization Assumptions

Expand Messages
  • Lance
    In 1986 during the prehistory of Hardness vs. Randomness, Sipser showed that if time does not have nontrivial space simulations one can derandomize. Given a
    Message 1 of 1 , Mar 30, 2006
    • 0 Attachment
      In 1986 during the prehistory of Hardness vs. Randomness, Sipser showed that if time does not have nontrivial space simulations one can derandomize. Given a (later-proved) assumption about extractor constructions
      If there is a constant c such that DTIME(2cn) is not contained in DSPACE(2.99cn) then P=RP.
      Later results used hardness against nonuniform circuits to derandomize complexity classes. For example Impagliazzo and Wigderson show
      If E does not have circuits of size 2o(n) then P=BPP.
      where E=DTIME(2O(n)).

      I recently discovered that Peter Bro Miltersen in his derandomization survey (page 56) notes that you can use a uniform assumption, a weaker version of Sipser's assumption.

      If E is not contained is DSPACE(2o(n)) then E does not have circuits of size 2o(n) and thus P=BPP.
      Miltersen's proof works by searching all circuits, using the local checkability of E to verify the correctness of the circuit.

      You can even assume the circuits have access to QBF or Σ2p gates, the later an assumption we needed in a recent paper. Saying E is not contained in subexponential space is so much nicer than saying E does not have nonuniform subexponential-size circuits with Σ2p gates.

      Technical Note: For all of the above you need to assume the separations at all input lengths.

      --
      Posted by Lance to Computational Complexity at 3/30/2006 07:34:00 PM

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