MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What's the best result about derandomizing BPP which based on some uniform assumptions?

For instance, is there some one proved that BPP can be simulate in subexp time if EXP \not\eq BPP?

share|cite|improve this question

"In other words, randomness never speeds computation by more than a polynomial amount unless non-uniformity always helps computation more than polynomially for problems with exponential time complexity."

share|cite|improve this answer
This is derandomization under nonuniform assumption, isn't it? – Emil Jeřábek Mar 4 '11 at 12:31

If $\mathrm{EXP}\ne\mathrm{BPP}$, then every problem in BPP can be solved deterministically in subexponential time on almost every input: Basically, this says that you can trade nonuniformity in the assumption with approximability in the conclusion. There is a nice (although not quite recent) survey of various derandomization results by Kabanets:

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.