We show that RL is contained in L/O(n), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To prove our result we show how to take an ultra-low space walk on the Gabber-Galil expander graph due to Gutfreund and Viola.

We show that RL is contained in L/O(n), i.e., any language computable
in randomized logarithmic space can be computed in deterministic
logarithmic space with a linear amount of non-uniform advice. To
prove our result we show how to take an ultra-low space walk on
the Gabber-Galil expander graph.