Google Analytics

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!