By BPP/linear I refer to BPP machines with linear advice, which fulfills the promise when given the "correct" advice, and the derandomization should give us, say, a P/linear or (SUBEXP/linear) algorithm.

If we use non-uniform assumptions, I think classical results should work, because we can "fool" non-uniform adversaries.

However, using uniform assumptions, say $EXP\neq BPP$, non-trivial derandomization seems like a harder question.

Do there exist results regarding this kind of classes, not necessary BPP/linear?


1 Answer 1


I used the this scholar search, and the only result which seems somehow relevant is this:

Lance Fortnow, Adam Klivans, Linear Advice for Randomized Logarithmic Space, ECCC TR05-042, 2005.

Unfortunately, I think it is not exactly what you need. In particular, the main result of the paper is $\mathbf{RL} \subseteq \mathbf{L}/O(n)$. Yet I believe the techniques used there might be helpful in the case of your question.


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.