Computer Science/Discrete Mathematics Seminar II

In this talk, we will discuss additional details of the `SL=L' result, not covered by the first talk. We will focus, however, on the possibility of extending our techniques towards resolving the general RL vs. L question. In this direction we obtain the following results, jointly with Luca Trevisan and Salil Vadhan: 1. We exhibit a new complete problem for RL: essentially this is st-connectivity restricted to directed graphs for which the random walk is promised to have polynomial mixing time. 2. Generalizing our techniques from the undirected case to directed, biregular graphs (i.e., where all in-degrees and out-degrees are equal): we present a deterministic, log-space algorithm that given a directed graph G that is biregular, and two vertices s and t, finds a path between s and t if one exists. 3. Using the same techniques, 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.