# The power of randomized logspace with two-way access to the random tape

Let $\mathsf{ZPL}$/$\mathsf{RL}$/$\mathsf{BPL}$ denote the classes of the languages which are accepted (with zero/one-side/two-side error) by a logspace Turing machine with one-way access to the random tape.

Let $\mathsf{ZP^*L}$/$\mathsf{R^*L}$/$\mathsf{BP^*L}$ denote the corresponding classes by replacing one-way to two-way access. We have the normal inclusions $\mathsf{ZPL} \subseteq\mathsf{RL}\subseteq\mathsf{BPL}$ and $\mathsf{ZP^*L} \subseteq\mathsf{R^*L}\subseteq\mathsf{BP^*L}$.

In the following paper,

On Read-Once vs. Multiple Access to Randomness in Logspace, Noam Nisan, 1995

he prove that $\mathsf{BPL} \subseteq \mathsf{ZP^*L}$, which is rather surprising because it seems that two-way access may be stronger than the one-way access.

Question. Do we have any further results which demonstrate the power of two-way access randomized logspace?

## 1 Answer

Well, here are a couple of observations. There's a famous PRG by Nisan that fools $$\mathsf{BPL}$$-type algorithms with seed length $$O(\log^2 n)$$. Given two-way access to the seed, Nisan's PRG can be computed in space $$O(\log n)$$. Therefore, every language in $$\mathsf{BPL}$$ can be decided by a $$\mathsf{BP}^*\mathsf{L}$$-type algorithm that only uses $$O(\log^2 n)$$ random bits.

In fact, you can get the best of both worlds. By using the same technique that Nisan used to show $$\mathsf{RL} \subseteq \mathsf{SC}$$, one can show that every language in $$\mathsf{BPL}$$ can be decided by a $$\mathsf{ZP}^*\mathsf{L}$$-type algorithm that only uses $$O(\log^2 n)$$ random bits.

So in terms of the state of the art, two-way randomness is more powerful both qualitatively (two-sided error vs. zero-sided error) and quantitatively (polynomially many random bits vs. polylogarithmically many random bits). However, it seems likely that $$\mathsf{L} = \mathsf{BP}^*\mathsf{L}$$ and hence the two models are actually equivalent.