Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

We introduce a set of techniques that allow for efficiently generating in parallel many independent random walks in the number of rounds (i.e., parallel time) being only poly-logarithmic in the walks' length.
In the undirected case, we start our random walks from the stationary distribution, which implies that we approximately know the empirical distribution of their next steps. This allows for preparing continuations of random walks in advance and applying a doubling approach. As a result we can generate multiple random walks of length L in O(log L) rounds.

For directed graphs, our approach stems from our treatment of the PageRank Markov chain. We first compute the PageRank for the undirected version of the input graph and then slowly transition towards the directed case, considering convex combinations of the transition matrices in the process.
For PageRank, we achieve the following round complexities for damping factor equal to 1 − є: in O(log log n + log 1 / є) rounds for undirected graphs (with Õ(m / є^2) total space requirements), in Õ(log^2 log n + log 1/є) rounds for directed graphs (with Õ((m+n^{1+o(1)}) / poly(є)) total space). The round complexity of our result for computing PageRank has only logarithmic dependence on 1/є.

A joint work with Jakub Łącki, Krzysztof Onak and Piotr Sankowski.