Thursday, March 30, 2006

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.

1 comment:

  1. Lance,

    What happened to NC and the complexity theory as viewed with the parallelization glasses? Is someone doing tangible research with it? Would like to know.

    Thanks a lot!