Already solved the previous open problem? Well here’s another question that was raised at the IITK workshop.

In an earlier post, I sketched a result by [Das Sarma, Gollapudi, Panigrahy] that showed that it was possible to simulate a random walk of length with space and passes over the input stream where is the number of nodes. Is it possible to simulate such a random walk using space and a much smaller number of passes, say polylogarithmic in and ? The goal is either to show an algorithm or prove a lower bound.

Das Sarma et al. simulate random walks to approximate the probability distribution on the vertices of the graph after a random walk of length . What is the streaming complexity of approximating this distribution? What is the streaming complexity of finding the (approximately) most likely vertices after a walk of length ?

Finally, is it possible to sparsify the input graph so that performing random walks in the sparsified graph gives similar results to performing random walks in the original graph?

**BONUS! Moving pictures…** Words bore you? Well, you could check out the video of the open problems session for a richer multimedia experience. Apologies in advance that it’s not in 3D.

### Like this:

Like Loading...

*Related*

## 1 comment

Comments feed for this article

August 9, 2010 at 2:25 pm

AndrewAnd no, the previous open problem wasn’t this one: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

Nor, will there be guaranteed fame, fortune, and fabulous funds if you solve any of these data stream problems. Sorry.