Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem
Omer Reingold, Luca Trevisan, Salil Vadhan · 2005
Motivated by Reingold’s recent deterministic log-space algorithm for UNDIRECTED S-T CONNEC-TIVITY (ECCC TR 04-94), we revisit the general RL vs. L question, 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 biregular (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” biregular graphs. Roughly speaking, given a random seed of logarithmic length, the generator constructs, in log-space, a “short” pseudorandom walk that ends at an almostuniformly distributed vertex when taken in any consistently labelled biregular graph. 4. We prove that if our pseudorandom generator from Item 3 could be generalized to all biregular graphs (instead of just consistently labelled ones), then our complete problem from Item 1 can be solved in log-space and hence RL = L.