Pseudorandom Walks in Regular Directed Graphs and the RL vs. L Question
Motivated by Reingold's recent deterministic log-space algorithm
for Undirected S-T Connectivity (ECCC TR
04-94), we revisit the
general question of whether Randomized Logspace (RL) equals
Deterministic Logspace (L), obtaining the following results:
Joint work with Omer Reingold and Luca Trevisan.
- 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.
- Generalizing Reingold's techniques, we present a deterministic,
log-space algorithm that given a directed graph G that is regular (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.
- Using the same techniques as in Item 2, we give a "pseudorandom
generator" for random walks on "consistently labelled" directed regular
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 directed regular graph.
- We prove that if our pseudorandom generator from Item 3 could
be generalized to all directed regular graphs (instead of just
consistently labelled ones), then our complete problem from Item 1
can be solved in log-space and hence RL=L.