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

A long-standing open question in complexity theory is whether there are problems that randomized algorithms can solve using (asymptotically) less space than possible by any deterministic algorithm. An important special case of this question was recently resolved by Reingold (STOC `05), who gave a deterministic log-space algorithm for S-T Connectivity in Undirected Graphs, by “derandomizing” the known randomized log-space algorithm of Aleliunas et al. (1979).

Motivated by Reingold’s result, we revisit the general question of whether randomized log-space (RL) equals deterministic log-space (L). We show that to prove RL=L, it suffices to construct a “pseudorandom generator” for random walks on *directed* graphs that are *regular* (i.e. all in-degrees and out-degrees are equal). In addition, we exhibit such a pseudorandom generator for “consistently labelled” regular directed graphs. Thus, if the “consistent labelling” condition can be removed in the latter result, then RL=L.

The talk will assume no special background in complexity theory or derandomization. The main technical tools involved are mixing rates of non-reversible Markov chains, expander graphs, and a new generalization of the zig-zag graph product of Reingold, Vadhan, and Wigderson.

Joint work with Omer Reingold and Luca Trevisan.
Paper at http://eccc.uni-trier.de/eccc-reports/2005/TR05-022/index.html