What's the best result about derandomizing BPP which based on some uniform assumptions?
For instance, has someone proved that BPP can be simulated in subexp time if EXP $\not =$ BPP?
What's the best result about derandomizing BPP which based on some uniform assumptions?
For instance, has someone proved that BPP can be simulated in subexp time if EXP $\not =$ BPP?
If $\mathrm{EXP}\ne\mathrm{BPP}$, then every problem in BPP can be solved deterministically in subexponential time on almost every input: http://dx.doi.org/10.1006/jcss.2001.1780. 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, "Derandomization: A Brief Overview", http://www.cs.sfu.ca/~kabanets/papers/chapter.pdf.
cseweb.ucsd.edu/~russell/iw1.ps
"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."