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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
3
|
|
|
|
|
2
|
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." |
|||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
1
|
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: http://www.cs.sfu.ca/~kabanets/papers/chapter.ps. |
||
|
|
