Editing Open Problems:22

{{DISPLAYTITLE:Problem 22: Random Walks}}
{{Infobox
|label1 = Proposed by
|data1 = Rina Panigrahy
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/22
}}
The paper of Das Sarma, Gollapudi, and Panigrahy {{cite|DasSarmaGP-08}} shows a method for performing random walks in the streaming model. In particular, a random walk of length $l$ can be simulated
using $O(n)$ space and $O(\sqrt{l})$ passes over the input stream. Is it possible to simulate such a random walk using $\tilde O(n)$ space and a much smaller number of passes, say, at most polylogarithmic in $n$ and $l$? The goal is either to show an algorithm or prove a lower bound.

Das Sarma et al. {{cite|DasSarmaGP-08}} simulate random walks to approximate the probability distribution on the vertices of the graph after a random walk of length $l$. What is the streaming complexity of approximating this distribution? What is the streaming complexity of finding the $k$ (approximately) most likely vertices after a walk of length $l$?