Monthly Archive

A few weeks ago I attended a workshop on Coding, Complexity, and Sparsity at the University of Michigan. Thanks to the organizers (Anna Gilbert, Martin Strauss, Atri Rudra, Hung Ngo, Ely Porat, and S. Muthukrishnan) for not only putting together a great program but also for treating the speakers like celebrities! The place swarmed with autograph hunters, roads were closed, and security kept the paparazzi at bay… at least I think this was all for our benefit.

I gave a brief tutorial on data streams and my slides can be found here if you’re interested. One of the results I went through was for the -sampling problem introduced by [Cormode, Muthukrishnan, Rozenbaum] and [Frahling, Indyk, Sohler]. See also [Monemizadeh and Woodruff] and [Jowhari, Saglam, Tardos]. Here the set-up is that you see a sequence of updates to a length vector . These updates can increment or decrement entries of although for the talk I assumed that the entires themselves always remained non-negative. E.g., for the sequence

would result in the vector . An algorithm for -sampling should return an element chosen uniformly at random from the set . See the slides (or the original papers) for an algorithm using space. Anyhow, during the talk I mentioned there was a simple trick to determine whether

.

But I decided to leave it as an easy puzzle for which I’d give the answer later. Of course, I forgot. See the comments to this post for the answer.

Other things to check out:

• I just noticed that Martin Strauss has typed up some of the open questions from the workshop.
• Dick Lipton blogged about the workshop talk on (1+eps)-Approximate Sparse Recovery by David Woodruff, joint work with Eric Price.