You are currently browsing the monthly archive for August 2010.

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 $t$ with $\tilde{O}(n)$ space and $O(\sqrt{t})$ passes over the input stream where $n$ is the number of nodes. Is it possible to simulate such a random walk using $\tilde O(n)$ space and a much smaller number of passes, say polylogarithmic in $n$ and $t$? 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 $t$. 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 $k$?

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.