A zero-one SUBEXP-dimension law for BPP

We show that BPPBPP has either SUBEXPSUBEXP-dimension zero (randomness is easy) or BPP=EXPBPP=EXP (randomness is intractable).

Research highlights
► We show that BPPBPP has either SUBEXPSUBEXP-dimension zero (randomness is easy) or BPP=EXPBPP=EXP (randomness is intractable).
► This paper improves Melkebeek's zero-one law for BPP by strengthening the statement “randomness is easy” in two aspects.
► First by reducing the time-bounds of the martingales from polynomial to subpolynomial.
► Second by replacing measure with dimension.