[Computational Complexity] Uniform Derandomization Assumptions
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