CWI Cryptology Group

Abstract: A random walk on graph is a sequence of vertices v₀,v₁ ,... such that at time i the vertex v_i is selected uniformly at random from the neighbors of v_i-1 in the graph. The usefulness of a random walk often follows from the convergence of v_i to the stationary distribution. We will consider walks on graphs that use significantly less randomness and still are similar in some sense to a random walk. A natural definition of such a pseudorandom distribution guarantees that the individual distribution of each v_i-1 in the pseudorandom walk will be statistically close to the distribution of the same vertex in a random walk. We suggest an alternative definition that only guarantees that the distribution of v_i-1 converges to the stationary distribution in time that is polynomial in the mixing time of the random walk. We will discuss both these definitions (both for directed an undirected), and will focus on their close relation to the derandomization of small space algorithms (and in particular the RL vs. L problem)