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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\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."

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is derandomization under nonuniform assumption, isn't it? $\endgroup$
    – Emil Jeřábek
    Commented Mar 4, 2011 at 12:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .