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.


A research blog about data streams and related topics.

Recently Tweeted

  • Resolved to only take the elevator if I was carrying coffee that would spill if I took the stairs. Now drinking more coffee. 3 months ago
  • I always find it more efficient to schedule meetings for yesterday. 3 months ago
  • RT @TheOfficialACM: Daniel Spielman of @Yale and Shang-Hua Teng of @USC to receive #Gödel Prize for addressing efficiency of graph algorith… 4 months ago
  • RT @mrtz: Please stop calling John Nash the "Beautiful Mind" mathematician. It's like calling Turing the "Imitation Game" mathematician. 4 months ago
  • Any deadline sufficiently far in the future is indistinguishable from never. 4 months ago

Get every new post delivered to your Inbox.

Join 203 other followers