Difference between revisions of "Open Problems:22"
(Created page with "{{DISPLAYTITLE:Problem 22: Random Walks}} {{Infobox |label1 = Proposed by |data1 = Rina Panigrahy |label2 = Source |data2 = Kanpur 2009 |label3 = Sho...") |
|||
| (3 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | {{ | + | {{Header |
| − | + | |source=kanpur09 | |
| − | | | + | |who=Rina Panigrahy |
| − | | | ||
| − | |||
| − | |||
| − | |||
| − | |||
}} | }} | ||
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 | 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 | ||
| Line 12: | Line 7: | ||
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$? | 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$? | ||
| + | |||
| + | <b>Update</b>: See some progress in {{cite|ChenKPSSY21}}. | ||
Latest revision as of 14:52, 23 July 2021
| Suggested by | Rina Panigrahy |
|---|---|
| Source | Kanpur 2009 |
| Short link | https://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$?
Update: See some progress in [ChenKPSSY21].
