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