ECCC-Report TR05-022https://eccc.weizmann.ac.il/report/2005/022Comments and Revisions published for TR05-022en-usSat, 19 Feb 2005 10:00:42 +0200
Paper TR05-022
| Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem |
Omer Reingold,
Luca Trevisan,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2005/022Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (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 almost-uniformly 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.
Sat, 19 Feb 2005 10:00:42 +0200https://eccc.weizmann.ac.il/report/2005/022