Difference between revisions of "Open Problems:22"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (1 revision)
 
(2 intermediate revisions by one other user not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 22: Random Walks}}
+
{{Header
{{Infobox
+
|source=kanpur09
|label1 = Proposed by
+
|who=Rina Panigrahy
|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
 
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].