Pseudorandom Walks on Regular Digraphs
and the RL vs. L Problem

Omer Reingold, Luca Trevisan, and Salil Vadhan


We revisit the general RL vs. L question, obtaining the following results.

  1. Generalizing Reingold's techniques to directed graphs, we present a deterministic, log-space algorithm that given a regular (or, more generally, Eulerian) directed graph G and two vertices s and t, finds a path from s to t if one exists.
  2. If we restrict ourselves to directed graphs that are regular and consistently labelled, then we are able to produce pseudorandom walks for such graphs in logarithmic space (this result already found an independent application).
  3. We prove that if (2) could be generalized to all regular directed graphs (including ones that are not consistently labelled) then RL=L. We do so by exhibiting a new complete promise problem for RL, and showing that such a problem can be solved in deterministic logarithmic space given a log-space pseudorandom walk generator for regular directed graphs.

We interpret (1) as indicating that it is not reversibility per se which Reingold's techniques rely upon, but rather the fact that, in the undirected S-T connectivity problem, the graph may be assumed to be regular without loss of generality. On the other hand, as far as derandomizing RL via pseudorandom walks goes, we obtain by (3) that one can assume regularity without loss of generality. In other words, for this purpose, it is not necessary to develop a theory of pseudorandomness for arbitrary directed graphs
with unknown stationary distributions. The combination of (2) and (3) indicates that the only obstacle towards a full derandomization of RL is in handling arbitrary edge labels. It remains to be seen
how difficult this challenge is to overcome.


 [ back to Salil Vadhan's research]