Pseudorandom walks on regular digraphs 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 directed graph G (or, more generally, a digraph with Eulerian connected components) and two vertices s and t, finds a path between s and 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 L=RL. 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.

Authors

• Omer Reingold
• Luca Trevisan 0001
• Salil P. Vadhan

Keywords

• derandomization
• expander graphs
• mixing time
• space-bounded computation
• universal traversal sequence
• zig-zag product