4
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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."

$\endgroup$
1
  • $\begingroup$ This is derandomization under nonuniform assumption, isn't it? $\endgroup$ Mar 4, 2011 at 12:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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