Pseudorandom Walks in Regular Directed Graphs and the RL vs. L Question

Salil Vadhan
Harvard

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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.
Joint work with Omer Reingold and Luca Trevisan.