Computational Complexity

Thursday, March 30, 2006

 
Uniform Derandomization Assumptions

Posted by 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 (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.

7:34 PM #

1.  Anonymous says:  
   
   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!
   
   Amar
   

   3:16 AM, April 01, 2006