Problem 22: Random Walks

From Open Problems in Sublinear Algorithms
Revision as of 10:31, 17 October 2012 by Krzysztof Onak (talk | contribs) (Created page with "{{DISPLAYTITLE:Problem 22: Random Walks}} {{Infobox |label1 = Proposed by |data1 = Rina Panigrahy |label2 = Source |data2 = Kanpur 2009 |label3 = Sho...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Proposed by Rina Panigrahy
Source Kanpur 2009
Short link http://sublinear.info/22

The paper of Das Sarma, Gollapudi, and Panigrahy [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. [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$?