<p>I used the this <a href="http://scholar.google.com/scholar?q=%22linear%20advice%22%20derandomization&amp;um=1&amp;ie=UTF-8&amp;sa=N&amp;hl=en&amp;tab=ws" rel="nofollow">scholar search</a>, and the only result which seems somehow relevant is this:</p>

<p><a href="http://www.eccc.uni-trier.de/report/2005/042/" rel="nofollow">Lance Fortnow, Adam Klivans, Linear Advice for Randomized Logarithmic Space, ECCC TR05-042, 2005.</a></p>

<p>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.</p>

CC BY-SA 2.5
2010-09-26T16:03:02.593Z
2010-09-26T18:15:14.530Z
2010-09-26T18:15:14.530Z
Sadeq Dousti
<p>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.</p>

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

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

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

<cc.complexity-theory><derandomization><advice-and-nonuniformity>
Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?
Sebastian Ben Daniel
# Has the derandomization of slightly non-uniform classes, e.g BPP/linear, been studied?

(Asked by: username_0 on 2010-08-23)

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?

**Tags:** cc.complexity-theory, derandomization, advice-and-nonuniformity


---

## 1 answers

### Answer by username_1 on 2010-09-26. Score: 5 | Accepted answer

I used the this [scholar search](http://scholar.google.com/scholar?q=%22linear%20advice%22%20derandomization&um=1&ie=UTF-8&sa=N&hl=en&tab=ws), and the only result which seems somehow relevant is this:

[Lance Fortnow, Adam Klivans, Linear Advice for Randomized Logarithmic Space, ECCC TR05-042, 2005.](http://www.eccc.uni-trier.de/report/2005/042/)

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.


---

