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?


It follows from this PRG of Nisan and Zuckerman. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.