Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have polynomial mixing time.

2. Generalizing Reingold's techniques, we present a deterministic, log-space algorithm that given a directed graph G that is biregular (i.e., all in-degrees and out-degrees are equal) and two vertices s and t, finds a path between s and t if one exists.

3. Using the same techniques as in Item 2, we give a "pseudorandom generator" for random walks on "consistently labelled" biregular graphs. Roughly speaking, given a random seed of logarithmic length, the generator constructs, in log-space, a "short" pseudorandom walk that ends at an almost-uniformly distributed vertex when taken in any consistently labelled biregular graph.

4. We prove that if our pseudorandom generator from Item 3 could be generalized to all biregular graphs (instead of just consistently labelled ones), then our complete problem from Item 1 can be solved in log-space and hence RL=L.