and the RL vs. L Problem

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

- 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.

- 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).

- 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.

*Electronic Colloquium on Computational Complexity*, Technical Report TR05-22, February 2005. [official ECCC page] This version incorrectly used the term "biregular graph" instead of "regular digraph".- Revision, November 2005. [postscript][pdf]
- In
*Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC `06),*pages 457-466, May 2006. [official ACM page]

[ back to Salil Vadhan's research]