You are currently browsing the monthly archive for September 2011.

That time of year again… the list of accepted papers for SODA has been posted. Some of the papers that might be of (direct or indirect*) interest to the streaming/sketching crowd include:

  • Sublinear Time, Measurement-Optimal, Sparse Recovery For All [Porat, Strauss]
  • Analyzing Graph Structure via Linear Measurements [Ahn, Guha, McGregor]
  • Sparser Johnson-Lindenstrauss Transforms [Kane, Nelson]
  • On the communication and streaming complexity of maximum bipartite matching [Goel, Kapralov, Khanna]
  • The Shifting Sands Algorithm [McGregor, Valiant]
  • Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy [Phillips, Verbin, Zhang]
  • A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size [Onak, Ron, Rosen, Rubinfeld]
  • Optimal Column-Based Low-Rank Matrix Reconstruction [Guruswami, Sinop]
  • Simple and Practical Algorithm for Sparse Fourier Transform [Hassanieh, Indyk, Katabi, Price]
  • Sketching Valuation Functions [Badanidiyuru, Dobzinski, Fu, Kleinberg, Nisan, Roughgarden]
  • Width of Points in the Streaming Model [Andoni, Nguyen]

(*) I’m not entirely sure what metric I’m using to determine “indirect interest” but rest assured, once I know, I’ll let you know. There also might be some additions to the above list once I’ve seen the actual papers.

BONUS! Comments from the chair… The PC chair, Yuval Rabani, discusses the selection process. Other posts on the selected papers include this and that and can be found here and there.


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. 2 months ago
  • I always find it more efficient to schedule meetings for yesterday. 2 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