Open Problems:22 - Revision history

135.180.193.4 at 14:52, 23 July 2021

2021-07-23T14:52:17Z

Krzysztof Onak: updated header

2013-03-07T01:48:58Z

updated header

Krzysztof Onak at 05:17, 16 November 2012

2012-11-16T05:17:43Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:51Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 22: Random Walks}} {{Infobox |label1 = Proposed by |data1 = Rina Panigrahy |label2 = Source |data2 = Kanpur 2009 |label3 = Sho..."

2012-10-17T10:31:54Z

Created page with "{{DISPLAYTITLE:Problem 22: Random Walks}} {{Infobox |label1 = Proposed by |data1 = Rina Panigrahy |label2 = Source |data2 = Kanpur 2009 |label3 = Sho..."

New page

{{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$?

← Older revision		Revision as of 14:52, 23 July 2021
Line 7:		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}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Rina Panigrahy

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 22: Random Walks}}
+{{Header
-{{Infobox
+|title=Random Walks
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Rina Panigrahy
+|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

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)