You are currently browsing the category archive for the ‘accepted papers’ category.

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.

Streaming and sketching papers in the RANDOM/APPROX accepted list include:

  • Streaming Algorithms with One-Sided Estimation [Brody, Woodruff]
  • Everywhere-Tight Information Cost Tradeoffs for Augmented Index [Chakrabarti, Kondapally]
  • Almost Optimal Explicit Johnson-Lindenstrauss Transformations [Kane, Meka, Nelson]
  • Periodicity and Cyclic Shifts via Linear Sketches [Crouch, McGregor]
  • Sparse recovery with partial support knowledge [Do Ba, Indyk]

Papers accepted for STOC include:

Papers accepted for STACS include:

  • Spectral Sparsification in the Semi-Streaming Setting [Levin, Kelner]
  • Polynomial Fitting of Data Streams with Applications to Codeword Testing [McGregor, Rudra, Uurtamo]

The list of accepted papers for SODA has been posted. Stream papers include:

If your paper ended up on the list of excepted papers, remember that the STACS deadline is this Friday. And there’s always STOC.

Luca has just announced the accepted papers for FOCS. Papers that have direct or indirect connections to streaming and communication complexity include:

Abstracts can be found here. More pdfs can be found at My Brain is Open.

Accepted papers from ESA and RANDOM/APPROX are out. Papers related to streaming include:

The accepted list for ICALP has been posted. Some of the papers relevant to the blog include:

Also, following on from my post about the PODS accepted papers, I wanted to note that the best paper was awarded to [Kane, Nelson, Woodruff] for their data streams paper on “An Optimal Algorithm for the Distinct Elements Problem.” Congrats!

BONUS! A Challenge… So you’re done with your FOCS submission? Well, don’t dawdle, there are plenty of deadlines over the next week to keep you occupied. Who needs sleep?

A beer/beverage-of-choice to anyone who makes them all!

Some nifty stream results in the accepted list from PODS:

  • Optimal Sampling From Distributed Streams [Cormode, Yi, Zhang, Muthukrishnan]
  • Fast Manhattan Sketches in Data Streams [Nelson, Woodruff]
  • An Optimal Algorithm for the Distinct Elements Problem [Kane, Nelson, Woodruff]

I also like the look of the PODS tutorial on “Information Complexity” that will be presented by T. S. Jayram. This is one of the most important techniques for proving stream and communication lower bounds. Check out the abstract here.

UPDATE: “An Optimal Algorithm for the Distinct Elements Problem” received the PODS Best Paper Award. Congrats!

[FWIW, I also had a paper accepted but it was on differential privacy rather than data streams. Perhaps I should add “secrecy” as a semi-suitable synonym to subjoin to the blog’s “streams, sketches, samples, sensing” tagline. Or would that be silly?]

The accepted list from STOC has just been posted (thanks My Brain is Open). Streaming and communication complexity papers that caught my eye include:

Godel’s Lost Letter had a great post about [Magniez, Mathieu, Nayak] and I previously mentioned the main problem from [Braverman, Ostrovsky]. I have a soft spot for both papers because they resolve open problems from a couple of my previous papers (this one and that one if you’re interested.)


A research blog about data streams and related topics.

Recently Tweeted