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(2^cn) 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 2^o(n) then P=BPP.

where E=DTIME(2^O(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(2^o(n)) then E does not have circuits of size 2^o(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 Σ₂^p 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 Σ₂^p gates.

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