<p>It follows from <a href="https://www.cs.utexas.edu/~diz/pubs/space.pdf" rel="noreferrer">this PRG of Nisan and Zuckerman</a>. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be decreased to $O(S)$.</p>

<p>In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can derandomize the algorithm completely by enumerating over all possible coin tosses.</p>

CC BY-SA 4.0
2018-06-10T20:31:23.823Z
2018-06-10T20:31:23.823Z
Or Meir
<p>Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$. </p>

<p>My question is about a $BPL$ machine that uses only polylog many bits of randomness. In one of Goldreich's papers, it is mentioned in passing that a language decided by such a $BPL$ machine is actually in deterministic logspace $L$. But I am unable to find any explanations of this remark anywhere. </p>

<p>Why can it be derandomized completely in logspace?</p>

<cc.complexity-theory><complexity-classes><derandomization><space-bounded><logspace>
$BPL$ with polylog random bits is in $L$
BharatRam
# $BPL$ with polylog random bits is in $L$

(Asked by: username_0 on 2018-06-10)

Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.

My question is about a $BPL$ machine that uses only polylog many bits of randomness. In one of Goldreich's papers, it is mentioned in passing that a language decided by such a $BPL$ machine is actually in deterministic logspace $L$. But I am unable to find any explanations of this remark anywhere.

Why can it be derandomized completely in logspace?

**Tags:** cc.complexity-theory, complexity-classes, derandomization, space-bounded, logspace

---

## 1 answers

### Answer by username_1 on 2018-06-10. Score: 13

It follows from [this PRG of Nisan and Zuckerman](https://www.cs.utexas.edu/~diz/pubs/space.pdf). This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be decreased to $O(S)$.

In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can derandomize the algorithm completely by enumerating over all possible coin tosses.


---

