A zero-one SUBEXP-dimension law for BPP
We show that BPP has either SUBEXP-dimension zero (randomness is easy) or BPP = EXP (randomness is intractable). (C) 2011 Elsevier B.V. All rights reserved.
computational complexity complexity theory resource-bounded measure resource-bounded dimension derandomization